Teza Church-Turing se referă la conceptul de metodă eficientă, sistematică sau mecanică în logică, matematică și informatică. Este formulată ca o descriere a conceptului intuitiv de computabilitate și, în raport cu funcțiile recursive generale, este mai des numită teza lui Church. De asemenea, se referă la teoria funcțiilor calculabile de calculator. Teza a apărut în anii 1930, când computerele în sine nu existau încă. Mai târziu a fost numit după matematicianul american Alonso Church și colegul său britanic Alan Turing.
Eficiența metodei de a obține rezultatul
Primul dispozitiv care semăna cu un computer modern a fost Bombie, o mașină creată de matematicianul englez Alan Turing. A fost folosit pentru a descifra mesajele germane în timpul celui de-al Doilea Război Mondial. Dar pentru teza sa și formalizarea conceptului de algoritm, a folosit mașini abstracte, numite mai târziu mașini Turing. Teza prezintăinteres atât pentru matematicieni, cât și pentru programatori, deoarece această idee i-a inspirat pe creatorii primelor computere.
În teoria computabilității, teza Church-Turing este cunoscută și sub numele de conjectura despre natura funcțiilor calculabile. Acesta afirmă că pentru orice funcție calculabilă algoritmic pe numere naturale, există o mașină Turing capabilă să o calculeze. Sau, cu alte cuvinte, există un algoritm potrivit pentru acesta. Un exemplu binecunoscut al eficacității acestei metode este testul tabelului de adevăr pentru testarea tautologiei.
O modalitate de a obține orice rezultat dorit se numește „eficientă”, „sistematică” sau „mecanică” dacă:
- Metoda este specificată în termeni de un număr finit de instrucțiuni exacte, fiecare instrucțiune este exprimată folosind un număr finit de caractere.
- Va rula fără erori, va produce rezultatul dorit într-un anumit număr de pași.
- Metoda poate fi efectuată de un om fără ajutor cu orice alt echipament decât hârtie și creion
- Nu necesită înțelegere, intuiție sau ingeniozitate din partea persoanei care efectuează acțiunea
Mai devreme în matematică, termenul informal „calculabil eficient” a fost folosit pentru a se referi la funcții care pot fi calculate cu creion și hârtie. Dar însăși noțiunea de calculabilitate algoritmică a fost mai intuitivă decât orice lucru concret. Acum a fost caracterizat de o funcție cu un argument natural, pentru care există un algoritm de calcul. Una dintre realizările lui Alan Turing a fostreprezentarea unui predicat formal exact, cu ajutorul căruia s-ar putea înlocui pe cel informal, dacă se folosește condiția de eficiență a metodei. Biserica a făcut aceeași descoperire.
Concepte de bază ale funcțiilor recursive
Schimbarea predicatelor lui Turing, la prima vedere, arăta diferit de cea propusă de colegul său. Dar, ca urmare, s-au dovedit a fi echivalente, în sensul că fiecare dintre ele selectează același set de funcții matematice. Teza Church-Turing este afirmația că această mulțime conține fiecare funcție ale cărei valori pot fi obținute printr-o metodă care satisface condițiile de eficiență. A existat o altă diferență între cele două descoperiri. Church a considerat doar exemple de numere întregi pozitive, în timp ce Turing și-a descris munca ca acoperind funcții calculabile cu o variabilă integrală sau reală.
Funcții recursive comune
Formularea originală a Church afirmă că calculul poate fi făcut folosind calculul λ. Acest lucru este echivalent cu utilizarea funcțiilor recursive generice. Teza Church-Turing acoperă mai multe tipuri de calcul decât se credea inițial. De exemplu, legat de automate celulare, combinatoare, mașini de înregistrare și sisteme de substituție. În 1933, matematicienii Kurt Gödel și Jacques Herbrand au creat o definiție formală a unei clase numite funcții recursive generale. Folosește funcții în care este posibil mai mult de un argument.
Crearea unei metodeλ-calcul
În 1936, Alonso Church a creat o metodă de determinare numită λ-calcul. El a fost asociat cu numerele naturale. În cadrul calculului λ, omul de știință a determinat codificarea acestora. Drept urmare, ele sunt numite numere ale Bisericii. O funcție bazată pe numere naturale a fost numită λ-calculabilă. A existat o altă definiție. Funcția din teza lui Church se numește λ-calculabilă în două condiții. Prima suna așa: dacă era calculată pe elemente Bisericii, iar a doua condiție era posibilitatea de a fi reprezentată de un membru al calculului λ.
Tot în 1936, înainte de a studia lucrările colegului său, Turing a creat un model teoretic pentru mașinile abstracte numite acum după el. Ei puteau efectua calcule manipulând personajele de pe bandă. Acest lucru se aplică și altor activități matematice găsite în informatica teoretică, cum ar fi calculul probabilistic cuantic. Funcția din teza lui Church a fost doar ulterior fundamentată cu ajutorul unei mașini Turing. Inițial, s-au bazat pe calculul λ.
Calculabilitatea funcției
Când numerele naturale sunt codificate în mod corespunzător ca secvențe de caractere, se spune că o funcție pe numere naturale este calculabilă prin Turing dacă mașina abstractă a găsit algoritmul necesar și a tipărit această funcție pe bandă. Un astfel de dispozitiv, care nu exista în anii 1930, va fi considerat în viitor un computer. Mașina Turing abstractă și teza lui Church au anunțat o eră a dezvoltăriidispozitive de calcul. S-a dovedit că clasele de funcții definite formal de ambii oameni de știință coincid. Prin urmare, ca urmare, ambele afirmații au fost combinate într-una singură. Funcțiile de calcul și teza lui Church au avut, de asemenea, o influență puternică asupra conceptului de computabilitate. De asemenea, au devenit un instrument important pentru logica matematică și teoria dovezilor.
Justificarea și problemele metodei
Există opinii contradictorii asupra tezei. Au fost strânse numeroase dovezi pentru „ipoteza de lucru” propusă de Church și Turing în 1936. Dar toate metodele sau operațiunile cunoscute pentru descoperirea de noi funcții efectiv calculabile din unele date erau legate de metode de construire a mașinilor, care nu existau atunci. Pentru a demonstra teza Church-Turing, se pleacă de la faptul că fiecare model realist de calcul este echivalent.
Datorită varietății diferitelor analize, aceasta este în general considerată a fi dovezi deosebit de puternice. Toate încercările de a defini mai precis noțiunea intuitivă de funcție efectiv calculabilă s-au dovedit a fi echivalente. Fiecare analiză care a fost propusă s-a dovedit că evidențiază aceeași clasă de funcții, și anume cele care sunt calculabile de mașinile Turing. Dar unele modele de calcul s-au dovedit a fi mai eficiente în ceea ce privește timpul și utilizarea memoriei pentru diferite sarcini. Mai târziu s-a remarcat că conceptele de bază ale funcțiilor recursive și teza lui Church sunt mai degrabă ipotetice.
„Teza M”
Este important să se facă distincția între teza lui Turing și afirmația că orice poate fi calculat de un dispozitiv de calcul poate fi calculat de către mașina lui. A doua opțiune are propria definiție. Gandhi numește a doua propoziție „Teza M”. Acesta spune așa: „Orice poate fi calculat de un dispozitiv poate fi calculat de o mașină Turing.” În sensul restrâns al tezei, este o propoziție empirică a cărei valoare de adevăr este necunoscută. Teza lui Turing și „Teza M” sunt uneori confundate. A doua versiune este în general incorectă. Au fost descrise diverse mașini condiționate care pot calcula funcții care nu sunt calculabile Turing. Este important de menționat că prima teză nu o implică pe a doua, dar este în concordanță cu falsitatea acesteia.
Implicația inversă a tezei
În teoria computabilității, teza lui Church este folosită ca o descriere a noțiunii de computabilitate de către o clasă de funcții recursive generale. Americanul Stephen Kleene a dat o formulare mai generală. El a numit parțial recursive toate funcțiile parțiale calculabile prin algoritmi.
Implicația inversă este denumită în mod obișnuit teza inversă a Bisericii. Constă în faptul că fiecare funcție recursivă a numerelor întregi pozitive este evaluată eficient. Într-un sens restrâns, o teză denotă pur și simplu o astfel de posibilitate. Și într-un sens mai larg, face abstracție de la întrebarea dacă această mașină condiționată poate exista în ea.
Computere cuantice
Conceptele de funcții calculabile și teza lui Church au devenit o descoperire importantă pentru matematică, teoria mașinilor și multe alte științe. Dar tehnologia s-a schimbat mult și continuă să se îmbunătățească. Se presupune că calculatoarele cuantice pot îndeplini multe sarcini comune cu mai puțin timp decât cele moderne. Dar rămân întrebări, cum ar fi problema opririi. Un computer cuantic nu poate răspunde. Și, conform tezei Church-Turing, nici un alt dispozitiv de calcul.
