Phenquestions
Turingov stroj središnji je teorijski konstrukt u računalnoj znanosti. Turingov stroj je apstraktni matematički model računanja. Korištenje Turingovih strojeva pomaže objasniti što je računanje razgraničenjem takozvanih „izračunavih funkcija."
Rano istraživanje logike Alana Turinga usredotočilo se na poznati neriješeni problem poznat kao Entscheidungsproblem. Entscheidungsproblem (približno preveden s njemačkog kao problem odluke) predložio je filozof i matematičar David Hilbert 1928. godine. Problem se pitao postoji li algoritam koji bi svaku izjavu odlučio formalnim jezikom.
Formalni jezik je sustav aksioma i pravila zaključivanja poput onih u aritmetičkoj ili logici prvog reda. Aksiomi mogu biti bilo koji simboli, a pravila zaključivanja mogu biti bilo koji popis pravila za manipulaciju tim simbolima. "Odlučivanje o svakoj izjavi" značilo je ili iznošenje je li izjava istinita / netačna ili iznošenje je li izjava izvedljiva / nedostupna. Teorem cjelovitosti Kurta Godela dokazao je da je algoritam koji odlučuje o valjanosti jednak učinkovitom postupku koji donosi odluku o izvedljivosti. Članak Alana Turinga iz 1936. godine „O izračunatim brojevima s primjenom na problem Entscheidungsproblem“ pokazao je negativan rezultat da je bilo nemoguće algoritamski odlučiti o svakoj tvrdnji u formalnom sustavu.
Alan Turing
Da bi dokazao negativan rezultat za problem Entscheidungs, Turing je trebao formalizirati pojam algoritma. Turingova formalizacija algoritma bio je matematički model računanja koji je kasnije postao poznat kao Turingov stroj. Turingov stroj ima konačan skup stanja u kojima stroj može biti. Turingov stroj ima beskonačno dugu traku koja je podijeljena u kvadrate. Na svakom kvadratu na traci nalazi se simbol izvučen iz konačnog skupa simbola. U bilo kojem trenutku izračuna, Turingov stroj očitava simbol na jednom kvadratu vrpce. Turingov stroj može taj simbol zamijeniti drugim simbolom i pomaknuti se na kvadrat udesno ili u kvadrat lijevo. Radnja koju Turingov stroj poduzima automatski se određuje stanjem u kojem je stroj. Nakon što se dogodi zamjenski simbol i prijeđe na drugo kvadratno djelovanje, Turingov stroj može prijeći u drugo stanje. Svaka različita država ima različit skup pravila o tome kako zamijeniti simbole i u kojem se smjeru kretati.
Rijetka fizička izvedba dizajna Turingova stroja (bez beskonačne vrpce)
Kanonska formulacija Turingova stroja obično se sastoji od binarne abecede od isključivo 0s i 1s. Ova formulacija odgovara intuiciji suvremenih računalnih programera, s obzirom na to da sva moderna računala koriste binarno. Zapravo su Turingovi strojevi neutralni s obzirom na veličinu abecede simbola. Turingov stroj također može koristiti bilo koji simbol, bilo numerički ili izvučen iz bilo koje druge vrste abecede, kao što su slikovni simboli ili latinična abeceda. Bilo koja formulacija svake moguće konačne abecede dokazivo se svodi na binarni Turingov stroj.
Turingovi strojevi pretpostavljaju da je na raspolaganju beskonačna količina memorije. Nijedan stvarni fizički instalirani stroj ne može ispuniti ovaj zahtjev da bude Turingov stroj. Turingov stroj također pretpostavlja potencijalno beskonačno puno vremena koji se može potrošiti računajući funkciju. Te su pretpostavke napravljene kako bi generirale najopsežniju klasu mogućih funkcija za Turingovu definiciju izračunatih funkcija. Turingove izračunate funkcije su bilo koje funkcije koje Turingov stroj može izračunati. Mnoge od ovih izračunljivih funkcija možda nikada neće moći izračunati nijedan fizički instaliran stroj jer im je potrebno previše vremena ili memorije.
Church-Turingova teza tvrdi da je ekvivalentnost izračunatih funkcija i funkcija koje Turingov stroj može izračunati. To podrazumijeva da se sve funkcije koje Turingovi strojevi ne mogu izračunati niti jednom drugom metodom. David Hilbert očekivao je pozitivan odgovor na problem Entscheidungs, što bi značilo da su svi problemi izračunljivi. Turingov rezultat doveo je do otkrića mnogih neuobičajenih problema.
Najpoznatiji neuobičajeni problem je problem zaustavljanja. Problem zaustavljanja problem je stvaranja algoritma koji u općenitom slučaju može odlučiti hoće li se računalni program s njegovim unosom zaustaviti ili nastaviti zauvijek. Iako postoje specifični slučajevi u kojima se problem Halting može riješiti, on se ne može riješiti za svaki računalni program s bilo kojim unosom. Ovaj rezultat imao je važne posljedice za računalno programiranje, jer računalni programeri moraju biti svjesni mogućnosti beskonačnih petlji i nemogućnosti otkrivanja svih beskonačnih petlji prije pokretanja svojih programa.
Sljedeća implikacija Turingova stroja je mogućnost univerzalnih Turingovih strojeva. Implicitni u Turingovom dizajnu koncept je pohrane programa koji modificira podatke uz podatke koje modificira. To je sugeriralo mogućnost računala opće namjene i programabilnih programa. Moderna računala su obično univerzalni Turingovi strojevi u smislu da se mogu programirati za pokretanje bilo kojeg algoritma. Time je eliminirana potreba za različitim hardverom za svaki potencijalni računalni program i uvedena je razlika između hardvera i softvera.
Model Turingova stroja izravno je doveo do izuma računala, ali to nije isti nacrt koji se koristi za projektiranje modernih računala. Von Neumannova arhitektura koja se koristi kao nacrt modernih računala koristi koncept pohranjenog programa implicitno u Turingovom modelu stroja, ali se razlikuje od ostatka Turingova modela stroja na nekoliko važnih načina. Najveće razlike su u tome što von Neumannova arhitektura ne koristi glavu za čitanje i pisanje, već umjesto toga uključuje višestruke registre, memoriju slučajnog pristupa, sabirnice podataka, mali skup osnovnih strojnih uputa i mogućnosti obrade više bitova. Von Neumannova arhitektura također izričito omogućuje specijalizirane uređaje za ulaz i izlaz kao što su tipkovnice i monitori.
Model Turingova stroja bio je prvi matematički model računanja. Dovelo je izravno do izuma fizičkih računala. Fizička računala imaju iste mogućnosti koje imaju Turingovi strojevi, pod pretpostavkom ograničenih memorije i vremenskih ograničenja stvarnih proračuna. Turingova formulacija još uvijek igra središnju ulogu u proučavanju računanja. Računalni znanstvenici i dalje su aktivno uključeni u istraživanje mogu li Turingovi strojevi izračunati određene funkcije.
