autorii mei preferați (David Deutsch, Roger Penrose și Douglas Hofstadter) se adâncesc cu toții în teza Bisericii-Turing a teoriei computaționale și, mai important, cea mai puternică interpretare a acesteia: principiul Turing. În această postare voi explica mai întâi teza Church-Turing în termeni laici.
pe vremea când lucram la diploma de informatică, am studiat mașinile Turing și teza Church-Turing în clasa mea de introducere în teoria computațională. Atunci am crezut că a fost o mare pierdere de timp. Am vrut doar să programez calculatoare și nu mi-a păsat mai puțin de acest tip Turing mort de mult (nici de acest tip de Biserică), nici de mașinile sale teoretice stupide.
acum, că înțeleg ramificațiile filosofice ale tezei Church-Turing, aș fi vrut să fiu atent în clasă! Deoarece teza Church-Turing, dacă este adevărată, are unele ramificații filosofice profunde și ar putea să ne spună și ceva despre natura profundă și specială a realității.
automate Finite
toate textele și clasele despre teoria calculului încep cu ceva numit „automate Finite.”Ideea de bază din spatele lor este destul de ușoară. Vă imaginați doar o mașină simplă care este capabilă să facă alegeri și să se deplaseze între state. Iată un exemplu de unul foarte simplu care reprezintă „logica” unui turnichet acționat cu monede.
în engleză simplă, aceasta spune că dacă încercați să împingeți printr-un turnichet blocat, nu puteți dacă nu ați introdus mai întâi o monedă. Dacă ați pus într-o monedă, dar nu au împins prin încă, monede suplimentare doar lăsați-l într-o stare deblocat. Dacă ați pus o monedă, atunci puteți împinge. Apoi se blochează din nou pentru următoarea persoană.
a fost probabil mai ușor de înțeles din diagramă decât din descriere.
automatele Finite sunt capabile să îndeplinească o logică mult mai complicată decât aceasta. Dar acest lucru ar trebui să vă ofere o senzație de bază pentru modul în care funcționează automatele finite.
un lucru de remarcat este că un Automat finit, ca cel de mai sus, este pur teoretic, deoarece există doar ca o grămadă de bule și linii pe o bucată de hârtie. Nu este ca și cum ar exista o mică „mașină automată finită” în interiorul turnichetului care ia aceste decizii. Sau poate ar trebui să spun în schimb că turnichetul în sine este mașina automată finită.
dacă ne-am dori cu adevărat, am putea construi probabil o mașină în viața reală care ar fi un Automat finit.Nimic nu împiedică pe cineva să o construiască ca o mașină reală în viața reală și apoi să o instaleze în turnichet. Acesta nu este cel mai ieftin mod de a face acest lucru.
deci, orice ” program „pe care îl faceți ca desen al unui Automat finit poate fi transformat într-un” calcul ” din viața reală care funcționează cu adevărat. Importanța diferenței dintre o mașină de calcul care poate exista de fapt (ca un Automat finit) și una care este doar ipotetică și încalcă legile fizicii devine importantă într-un moment.
mașini mai puternice
pe măsură ce o clasă în teoria computațională progresează, elevii sunt introduși în mașini din ce în ce mai complexe, care sunt mai puternice decât automatele Finite. După cum arată figura din dreapta, următoarea cea mai puternică este Automata Pushdown (PDA). Un PDA este într-adevăr doar un DFA cu adăugarea unui fel de „memorie”. Această memorie permite unui PDA să creeze și să ruleze calcule (sau programe) pe care un DFA nu le poate.
punctul cheie este doar că există anumite tipuri de programe care pot fi scrise pentru un PDA care nu pot fi scrise pe un Automat finit determinist (DFA). Cu alte cuvinte, PDA-urile sunt „mai puternice” decât DFA-urile, deoarece pot exprima clase de „programe” pe care DFA-urile nu le pot.
deci există o relație între DFA-uri și PDA-uri în termeni de „putere de calcul”.”Și anume este posibil să se demonstreze că orice program scris pe un DFA poate fi scris și pe un PDA, dar că inversul nu este adevărat.
dovada este în dovada
dovada că un PDA poate rula orice poate face un DFA venind cu o schemă prin care logica unui DFA poate fi mapată la un PDA. Deoarece un PDA este doar un DFA cu memorie, acest lucru nu este greu de făcut — pur și simplu nu utilizați „funcția de memorie”.
dar cum rămâne cu reversul? Putem dovedi că este imposibil să luăm anumite tipuri de „programe” scrise pentru un PDA și să le traducem într-un DFA? Adică, există o dovadă că automatele Pushdown nu pot fi mapate la o automată finită? Sau doar presupunem că un Automat finit este mai puțin puternic decât un automat de împingere pentru că nu știm în prezent o modalitate de a mapa un PDA înapoi la un FDA? Poate că există o modalitate de a mapa PDA-urile la FDA-uri și poate că nimeni nu a descoperit încă cum să facă asta? Nu e măcar o posibilitate?
după cum se dovedește, este posibil să se demonstreze că un PDA poate rula anumite tipuri de programe pe care un DFA nu le poate. Modul în care ați face-o este că ați găsi un calcul (adică. un program) pe care le puteți dovedi un DFA nu poate calcula și apoi să demonstreze că un PDA poate calcula.
puterea de calcul a unei mașini
acest fapt — că există mașini logice mai puternice (PDA) și mai puțin puternice (DFA) — este interesant în sine.
dar duce la o întrebare filosofică: există un astfel de lucru ca „cea mai puternică mașină de calcul?”
dacă ar exista o astfel de” mașină cea mai puternică”, cum am ști că o mașină specifică propusă se întâmplă să fie ” cea mai puternică?”Sau există doar diferite tipuri de mașini de calcul disponibile și trebuie să o alegeți pe cea potrivită pentru slujbă?
mașini Turing
deci, ce mașină este mai puternică decât un PDA?
după cum ar fi avut-o Istoria, cam în același timp au fost propuse două tipuri foarte diferite de „mașini” care erau ambele demonstrabil mai puternice decât PDA-urile.
unul a fost mașina Turing a lui Alan Turing. Cealaltă nu era atât o mașină, cât un set inteligent de notații dezvoltate de Biserica Alonzo care servea aceluiași scop ca dezvoltarea unei mașini. Dintre aceste două „mașini”, mașina Turing este conceptual mai ușor de predat, deci de obicei aceasta este mașina care este predată într-un curs de teorie computațională.
mașinile Turing sunt mici mașini teoretice amuzante care au un cap de citire/scriere și o bandă de hârtie (ipotetică) pe care o poate citi sau scrie. Pe baza a ceea ce citește mașina Turing, aceasta pune mașina Turing într-o stare de acțiune care efectuează un fel de combinație de sarcini constând fie în mișcarea capului de citire/scriere înainte sau înapoi, citirea dintr-o nouă poziție pe bandă, fie scrierea unei noi poziții pe bandă. O mașină Turing arată astfel:
mașini Turing și computere moderne
un lucru interesant este că o mașină Turing este, în ciuda aparențelor de suprafață, de fapt destul de asemănătoare cu un computer modern. Într-un computer modern, unitatea centrală de procesare (CPU) este echivalentă cu capul de citire/scriere al unei mașini Turing. Cipurile de memorie (RAM sau ROM) sunt foarte asemănătoare cu celulele benzii lungi de hârtie pe care mașina de strunjire o poate citi sau scrie. Deci, computerele moderne par a fi aproximativ echivalente cu o mașină Turing.
un computer modern are un avantaj față de mașina Turing. Un computer modern nu trebuie să se deplaseze dintr-o celulă a „memoriei” sale în ordine secvențială, așa cum o face o mașină Turing.
faptul că o mașină Turing poate muta o singură celulă la un moment dat pare o limitare semnificativă, nu-i așa? Tocmai am văzut cum unele mașini sunt logic ‘mai puternice’ decât altele: un PDA poate efectua sarcini computaționale pe care un FDA nu le poate face. Deci, poate că există mașini care sunt mai puternice decât mașinile Turing care pot îndeplini sarcini pe care mașinile Turing nu le pot face? Și poate computerul modern – datorită capacității lor de a sări în jurul memoriei, mai degrabă decât de a trece de la celulă la celulă secvențial — poate rula unele programe pe care o mașină Turing nu le poate face?
de fapt, computerele moderne au de fapt o putere mai puțin expresivă decât o mașină Turing în virtutea faptului că mașinile Turing au fost concepute ca având o bandă de hârtie infinit de lungă (adică memorie infinită) unde, ca un computer din viața reală, va avea întotdeauna memorie finită. Cu toate acestea, în general, acest lucru face o diferență foarte mică în ce tipuri de calcule se poate efectua, deoarece ființele umane nu sunt în general interesate de calcule infinit de lungi care dau rezultate infinit de lungi. De aceea spun că computerele moderne și mașinile Turing sunt „aproximativ” echivalente. De fapt, atâta timp cât vă asumați orice dimensiune arbitrară, dar finită a memoriei, acestea sunt exact echivalente în ceea ce privește tipurile de programe pe care le pot rula.
teza Bisericii Turing: mașina Turing = puterea logică maximă
dar ce zici de Biserica săracă Alonzo? Bietul lui „mașină” uitat, deoarece mașinile Turing sunt mai ușor de a preda. Este mașina lui capabilă să exprime unele calcule /programe pe care o mașină Turing nu le poate face sau invers?
nu ar fi o coincidență stelară dacă s-ar întâmpla ca Alan Turing și Alonzo Church să creeze două tipuri complet diferite de mașini de calcul teoretice și s-ar întâmpla ca acestea să fie exact identice în ceea ce privește tipurile de calcule pe care le-ar putea efectua?
deci, imaginați-vă surpriza tuturor când Alan Turing a fost capabil să producă o dovadă că orice program scris pentru o mașină Turing ar putea fi scris și pentru o mașină Biserică și, de asemenea, o dovadă că orice program scris pentru o mașină Biserică ar putea fi scris și pentru o mașină Turing.
de fapt, există o serie de tipuri propuse de mașini de calcul teoretice. De exemplu, teoreticienii au încercat să permită unei mașini Turing să aibă mai multe benzi cu care să citească/scrie. Au încercat chiar să permită unei mașini Turing o ‘foaie’ 2-dimensională cu care să citească și să scrie. Teoreticienii au încercat tot felul de îmbunătățiri ale mașinilor Turing (și mașinilor bisericești).
și până acum a fost posibil să se producă o dovadă pentru fiecare dintre ele că sunt echivalente cu o mașină Turing simplă.
asta pare o coincidență sălbatică, nu-i așa? Și ar fi o coincidență sălbatică dacă nu există o limită superioară la ce tipuri de calcul pot fi efectuate.
dacă există o astfel de limită superioară, atunci nu ar fi deloc o coincidență faptul că mașina Turing și mașina Bisericii și toate celelalte mașini de calcul propuse se întâmplă să aibă aceeași putere de calcul, deoarece, de fapt, motivul pentru care toate sunt echivalente este pentru că am atins limita superioară a puterii de calcul.
dar putem dovedi că nu există o mașină de calcul acolo — una pe care pur și simplu nu am descoperit — o încă-care să aibă capacitatea de a efectua calcule pe care o mașină Turing nu le poate face?
cum anume am produce o astfel de dovadă? Faptul este că nu putem dovedi că nu există nimic mai puternic decât o mașină Turing. Deci, cine știe, poate că există.
dar adevărul este că nu putem găsi (sau inventa) astfel de mașini.
Deci, după eforturi considerabile încercând și eșuând, pentru a găsi o modalitate de a îmbunătăți puterea mașinilor Turing, în cele din urmă teza Church-Turing a fost acceptată, chiar dacă nu s-a dovedit a fi adevărată. Teza Church-Turing spune în esență ceva de genul acesta:
nu este posibil de a veni cu orice fel de mașină de calcul, care poate efectua un program logic că o mașină Turing simplu vechi nu poate.
sau cu alte cuvinte:
mașinile Turing și echivalentele lor sunt cele mai puternice tipuri posibile de mașini de calcul și nu există altele mai puternice acolo despre care pur și simplu nu știm încă.
după ani și ani de cercetări asupra acestei teze, această teză încă se menține practic. Vom vedea mai târziu că a existat oarecum o modificare a tezei cu introducerea computerelor cuantice teoretice. Dar, practic, Teza este valabilă și astăzi. Nimeni nu a venit vreodată cu o modalitate de a depăși performanțele mașinilor Turing atunci când vine vorba de expresivitate logică. Mașinile Turing sunt încă campionul în exercițiu.
deci acum înțelegeți teza Church-Turing. Cu toate acestea, teza Church-Turing nu este într-adevăr destul de echivalentă cu principiul Turing. Deci, într-o postare viitoare, voi dezvolta care este diferența și care sunt ramificațiile filosofice.
Notează
Principiul Turing. Așa numit de Roger Penrose, care nu crede în ea (cel puțin nu în forma actuală). A fost dezvoltat în principiul Turing-Deutsch de David Deutsch, care crede în el, cel puțin în forma sa.) (A se vedea articolul din Wikipedia pentru mai multe detalii)