Phenquestions
Turingov stroj je osrednji teoretični konstrukt v računalništvu. Turingov stroj je abstraktni matematični model računanja. Uporaba Turingovih strojev pomaga razložiti, kaj je izračunavanje, tako da razmeji tako imenovane »računske funkcije."
Zgodnje raziskave logike Alana Turinga so se osredotočile na slavni nerešeni problem, znan kot Entscheidungsproblem. Entscheidungsproblem (grobo prevedeno iz nemščine kot odločitveni problem) je leta 1928 predlagal filozof in matematik David Hilbert. Težava se je vprašala, ali obstaja algoritem, ki bi odločil za vsako izjavo v formalnem jeziku.
Formalni jezik je sistem aksiomov in pravil sklepanja, kot so tista v aritmetiki ali logiki prvega reda. Aksiomi so lahko kateri koli simboli in pravila sklepanja so lahko kateri koli seznam pravil za manipulacijo s temi simboli. »Odločanje o vsaki izjavi« je pomenilo bodisi izpis, ali je stavek resničen / neresničen, bodisi izpis, ali je stavek izpeljan / nedosegljiv. Izrek popolnosti Kurta Godela je dokazal, da je algoritem, ki odloča o veljavnosti, enakovreden učinkovitemu postopku odločanja o izpeljanosti. Prispevek Alana Turinga iz leta 1936 "O računskih številkah z aplikacijo na problem Entscheidungsproblem" je dokazal negativen rezultat, da je bilo nemogoče algoritemsko odločiti za vsako trditev v formalnem sistemu.
Alan Turing
Da bi dokazal negativen rezultat za problem Entscheidungs, je moral Turing formalizirati pojem algoritma. Turingova formalizacija algoritma je bil matematični model računalništva, ki je kasneje postal znan kot Turingov stroj. Turingov stroj ima končni nabor stanj, v katerih je lahko stroj. Turingov stroj ima neskončno dolg trak, ki je razdeljen na kvadrate. Na vsakem kvadratu na traku je simbol, narisan iz končnega nabora simbolov. V vsakem trenutku pri izračunu Turingov stroj bere simbol na enem kvadratu traku. Turingov stroj lahko ta simbol nadomesti z drugim simbolom in se premakne na kvadrat v desno ali kvadrat v levo. Ukrep Turingovega stroja samodejno določi stanje, v katerem je stroj. Po zamenjavi simbola in premiku na drugačno kvadratno akcijo lahko Turingov stroj preide v drugo stanje. Vsako različno stanje ima različna pravila glede tega, kako zamenjati simbole in v katero smer se premakniti.
Redka fizična izvedba zasnove Turingovega stroja (brez neskončnega traku)
Kanonična formulacija Turingovega stroja je običajno sestavljena iz binarne abecede izključno 0s in 1s. Ta formulacija ustreza intuiciji sodobnih računalniških programerjev, saj vsi sodobni računalniki uporabljajo binarno. Dejansko so Turingovi stroji nevtralni glede na velikost abecede simbolov. Turingov stroj lahko uporablja tudi kateri koli simbol, bodisi številčen bodisi iz katerega koli drugega tipa abecede, kot so slikovni simboli ali latinična abeceda. Kakršno koli formulacijo vseh možnih končnih abeced je dokazljivo mogoče zmanjšati na binarni Turingov stroj.
Turingovi stroji domnevajo, da je na voljo neskončno veliko pomnilnika. Noben pravi fizično instantiran stroj ne more izpolniti te zahteve, da bi bil Turingov stroj. Turingov stroj predvideva tudi, da lahko za izračun funkcije porabi neomejeno veliko časa. Te predpostavke so bile narejene za ustvarjanje najbolj obsežnega razreda možnih funkcij za Turingovo definicijo izračunanih funkcij. Turingove računske funkcije so vse funkcije, ki jih lahko izračuna Turingov stroj. Številne od teh izračunanih funkcij morda nikoli ne bo mogoče izračunati na nobenem fizično izdelanem računalniku, ker zahtevajo preveč časa ali pomnilnika.
Church-Turingova teza trdi o enakovrednosti izračunanih funkcij in funkcij, ki jih lahko izračuna Turingov stroj. To pomeni, da vseh funkcij, ki jih Turingovi stroji ne morejo izračunati, ni mogoče izračunati z nobeno drugo metodo. David Hilbert je pričakoval pozitiven odgovor na problem Entscheidungs, kar bi pomenilo, da so vsi problemi izračunani. Rezultat Turinga je privedel do odkritja številnih neznanskih težav.
Najbolj znana težava je problem Halting. Problem zaustavitve je problem ustvarjanja algoritma, ki lahko v splošnem odloči, ali se bo računalniški program z njegovim vhodom ustavil ali nadaljeval za vedno. Čeprav obstajajo posebni primeri, ko je problem Halting mogoče rešiti, ga ni mogoče rešiti za vsak računalniški program s kakršnim koli vhodom. Ta rezultat je imel pomembne posledice za računalniško programiranje, saj se morajo računalniški programerji zavedati možnosti neskončnih zank in nemogoče zaznati vse neskončne zanke pred izvajanjem svojih programov.
Druga implikacija Turingovega stroja je možnost univerzalnih Turingovih strojev. Impliciten pri Turingovi zasnovi je koncept shranjevanja programa, ki spreminja podatke poleg podatkov, ki jih spreminja. To je nakazovalo možnost splošnih in vnovičnih programov. Sodobni računalniki so običajno univerzalni Turingovi stroji v smislu, da jih je mogoče programirati za izvajanje katerega koli algoritma. To je odpravilo potrebo po drugačni strojni opremi za vsak potencialni računalniški program in uvedlo razliko med strojno in programsko opremo.
Model Turingovega stroja je neposredno pripeljal do izuma računalnikov, vendar to ni isti načrt, ki se uporablja za oblikovanje sodobnih računalnikov. Von Neumannova arhitektura, ki se uporablja kot načrt sodobnih računalnikov, uporablja koncept shranjenega programa, impliciten v modelu Turingovega stroja, vendar se na več pomembnih načinov razlikuje od ostalega Turingovega modela stroja. Največje razlike so v tem, da von Neumannova arhitektura ne uporablja bralno-pisalne glave in namesto tega vključuje več registrov, pomnilnik z naključnim dostopom, podatkovna vodila, majhen nabor osnovnih strojnih navodil in več bitne zmogljivosti obdelave. Von Neumannova arhitektura izrecno omogoča tudi posebne vhodne in izhodne naprave, kot so tipkovnice in monitorji.
Model Turingovega stroja je bil prvi matematični model računanja. Neposredno je pripeljalo do izuma fizičnih računalnikov. Fizični računalniki imajo vse enake zmogljivosti, kot jih imajo Turingovi stroji, ob predpostavki, da imajo dejanski izračun omejene pomnilnik in čas. Turingova formulacija ima še vedno osrednjo vlogo pri preučevanju računalništva. Računalniški znanstveniki še vedno aktivno sodelujejo pri raziskovanju, ali določene funkcije izračunajo Turingovi stroji.
