Teorija izračunljivosti i Tjuringove mašine

Uvod u teoriju izračunljivosti

• Kontekst unutar savremene logike: Teorija izračunljivosti predstavlja jednu od ključnih disciplina savremene logike, pored teorije dokaza, teorije modela, teorije značenja i teorije skupova. Iako se ranije samo usputno pominjala (npr. kod funkcionalno potpunih skupova veznika), ona predstavlja temelj za razumevanje odnosa između logike i informatike.
• Definicija i predmet proučavanja:     - Teorija izračunljivosti primarno istražuje pod kojim uslovima je određena funkcija ili formula izračunljiva.     - Fokus je na procesu transformacije ulaznih vrednosti (input) u precizno određene izlazne vrednosti (output).     - Izračunljivost se definiše kao formalizovana ideja samog postupka računanja.
• Uslovi za izračunljivost funkcije: Da bi se funkcija smatrala izračunljivom, moraju biti zadovoljeni strogi kriterijumi:     - Postojanje algoritma: Mora postojati precizan i definisan skup koraka za utvrđivanje izlaznih vrednosti.     - Tačnost i ponovljivost: Algoritam mora uvek davati tačan rezultat i biti primenljiv u istim uslovima sa istim uspehom.     - Postupnost: Proces ne sme sadržati nikakve „intuitivne skokove“; svaki korak mora logički slediti iz prethodnog.
• Apstrakcija od psihološkog procesa:     - Računanje u teoriji izračunljivosti je potpuno nezavisno od subjekta koji ga izvodi.     - Nebitno je da li operaciju vrši genije mentalnom aritmetikom, učenik na papiru ili računar putem binarnih operacija ($0$ i $1$).     - Cilj je proučavanje same strukture računanja, a ne psiholoških aspekata agenta koji računa.
• Pioniri discipline: Ključne figure koje su povezale logiku i ranu informatiku su Alan Tjuring (Alan Turing) i Alonzo Čerč (Alonzo Church).

Tjuringova mašina

• Koncept: Osmišljena od strane Alana Tjuringa u prvoj polovini 20. veka, Tjuringova mašina predstavlja apstraktni model aparata za računanje.
• Komponente Tjuringove mašine:     - Beskonačna traka: Podeljena je na segmente (polja). U svaki segment može biti upisan jedan simbol koji predstavlja informaciju. Ova traka je direktna analogija savremenoj memoriji računara.     - Radna „glava“: Mehanizam koji se kreće duž trake. Može da čita upisane simbole, briše ih i upisuje nove. Odgovara funkciji procesora.     - Konačna tablica sa instrukcijama: Skup pravila koji diktira ponašanje glave na osnovu pročitanog simbola.         - Primer: Ako glava pročita simbol „\“, instrukcija može glasiti: „pomeri se za dva mesta ulevo i unesi simbol $\beta$“.         - Ovaj deo odgovara programskim instrukcijama u modernom softveru.     - Registar: Deo mašine koji beleži sva stanja kroz koja sistem prolazi tokom procesa.
• Varijacije i suština: Postoje verzije sa više glava ili više traka, ali sve su fundamentalno ekvivalentne u pogledu onoga što mogu da izračunaju.
• Svrha modela:     - Model nije nacrt za fizičku konstrukciju računara (fizički realizovana Tjuringova mašina bila bi spora i nezgrapna).     - Namera je bila da se definišu granice onoga što bilo koja mašina za računanje može da izvede.     - Model je primenljiv kako na neorganske sisteme (silicijumska jezgra), tako i na biološke sisteme (ljudski mozak).

Univerzalna Tjuringova mašina (UTM) i Čerč-Tjuringova teza

• Univerzalna Tjuringova mašina (UTM): Posebna vrsta mašine koja može da simulira rad bilo koje druge, prostije Tjuringove mašine. Ona u sebi sadrži resurse za izvršenje svakog mogućeg računanja.
• Moć UTM:     - UTM je najmoćniji teoretski model računara ne po brzini, već po opsegu izvodljivosti.     - Ako UTM ne može da reši određeni zadatak, to znači da ne postoji nijedan drugi računarski sistem koji bi to mogao.     - Do danas ne postoji poznata procedura računanja koja se ne može izvršiti na UTM, a može na nekom drugom modelu.
• Čerč-Tjuringova teza: Ova teza uspostavlja fundamentalnu paralelu između automatskog računanja i mišljenja (u algoritamskom smislu).     - Definicija: Funkcija je izračunljiva ako i samo ako je izračunljiva za Tjuringovu mašinu.     - Implikacije:         - Ako funkcija nije izračunljiva za Tjuringovu mašinu, ona nije izračunljiva ni za jedan drugi sistem (bilo organski mozak ili neorganski procesor).         - Napomena: Ovo se odnosi na algoritamske procese, dok kreativnost i intuicija nisu nužno obuhvaćeni ovim modelom.     - Status teze: Nije konkluzivno dokazana, ali postoji ogroman broj indikacija koje potvrđuju njenu ispravnost.

Problem zaustavljanja (Halting Problem)

• Definicija neizračunljivosti: Postoje funkcije za koje je dokazano da nisu izračunljive.
• Formulacija Halting problema: Pitanje je da li jedan računar može unapred da proceni da li će se za dati algoritam i date ulazne vrednosti proces završiti (haltovati) ili će mašina upasti u beskonačnu petlju.
• Praktična vrednost: Rešenje bi omogućilo softveru da razlikuje situaciju u kojoj je računar „zakucan“ od situacije u kojoj on samo vrši veoma složenu i dugotrajnu operaciju.
• Teoretski zakjučak: Odgovor na Halting problem je negativan; nemoguće je konstruisati opšti algoritam koji bi ovo rešavao za sve slučajeve.

Logički dokaz nemogućnosti rešenja Halting problema

• Metod dokaza: Posredni dokaz (reductio ad absurdum).
• Postavka hipotetičkog programa $H$:     - Pretpostavimo da postoji program $H$ koji rešava Halting problem.     - Ulaz $I1$: Algoritam koji proveravamo.     - Ulaz $I2$: Ulazne vrednosti za taj algoritam.     - Rezultat $H$: Ispisuje „haltuje“ ili „ne haltuje“.
• Problem simulacije: Ako program koji $H$ proverava ne haltuje, onda ni simuluacija unutar $H$ neće haltovati, što znači da $H$ nikada neće moći da izbaci odgovor „ne haltuje“. Vremensko ograničenje ovde ne pomaže, jer bi prekratak limit proglasio izračunljive procese neizračunljivim.
• Formalni dokaz kontradikcijom:     - Konstruišimo složeni program $X$ koji se sastoji od programa $H$ i dodatnog programa negacije $N$.     - Pravila za $N$:         - Ako $H$ kaže „haltuje“, $N$ se zakucava (beskonačna petlja).         - Ako $H$ kaže „ne haltuje“, $N$ ispisuje „haltuje“ i staje.     - Testiranje programa $X$ na samom sebi (Self-reference):         - Šta ako damo programu $X$ da proveri sopstveni kod (gde su i $I1$ i $I2$ zapravo $X$)?         - Scenario A: $H$ predvidi da će $X$ haltovati. Prema pravilu programa $N$, celi sistem $X$ će se tada zakucati. Ovo je kontradikcija onome što je $H$ predvideo.         - Scenario B: $H$ predvidi da $X$ neće haltovati. Prema pravilu programa $N$, sistem će ispisati „haltuje“ i stati. Opet dobijamo kontradikciju predviđanju koje je dao $H$.
• Zaključak dokaza: Budući da oba scenarija vode u logičku kontradikciju, program $H$ ne može postojati. Prema Čerč-Tjuringovoj tezi, to znači da nikada nećemo moći univerzalno da znamo da li je računar zaglavljen ili samo intenzivno radi.