Računalniki in Turingovi stroji

Na osnovi povedanega se zastavlja naslednje vprašanje: kako so Turingovi stroji vplivali na razvoj današnjih digitalnih računalnikov? Iz opisa lahko sklepamo, da je zgradba današnjih računalnikov zasnovana predvsem na intuitivnem razumevanju dogajanja pri ročnem računanju. Gledano s stališča ljudi, ki razvijajo in delajo računalnike, bi potem lahko zaključili, da so Turingovi stroji za praktično računalništvo nepomembni.

Nedvomno je res, da danes veliko ljudi uspešno dela na razvoju računalnikov ne da bi pri tem kakorkoli razmišljali o Turingovih strojih ali celo sploh kaj vedeli o njih. Zato je verjetno smiselno nekoliko podrobneje osvetliti zvezo med računalniki in Turingovimi stroji.

Najpomembnejša ugotovitev je, da noben računalnik ne more izračunati več kot univerzalni Turingov stroj. Vendar iz tega nikakor ne sledi, da bi morali računalnike graditi po vzoru na Turingove stroje. Prvič to ni mogoče, ker ima Turingov stroj neskončno dolg pomnilniški trak, ki ga v realnem svetu očitno ni. Kot bomo videli nekoliko kasneje, je ta težava za praktične namene pravzaprav zanemarljiva. Dosti bolj pomembna je ugotovitev, do katere lahko hitro pridemo s primerjavo kateregakoli resničnega računalnika s Turingovim strojem: celo najbolj preprost računalnik deluje neprimerno hitreje. Razlog za to je v tem, da je pri vseh računalnikih preprostost Turingovega stroja namerno žrtvovana za večjo hitrost in učinkovitost uporabe.

Morda je umestno na tem mestu povedati tudi naslednje. Vsakdo, ki se pritožuje nad nerodnost jo in počasnostjo programiranja na današnjih računalnikih, bi za tolažbo lahko poskusil, kako strahovito nerodno je na Turingovem stroju rešiti celo najpreprostejše probleme kot sta npr. seštevanje ali množenje dveh števil. Kljub temu je mogoče na razmeroma preprost način matematično strogo dokazati, da lahko univerzalni Turingov stroj simulira delovanje vsakega obstoječega računalnika.

Za praktično vse realne probleme je mogoče dokazati, da velja tudi obratna zveza. Vsak računalnik z dovolj velikim glavnim pomnilnikom, ki igra vlogo pomnilniškega traku, lahko igra vlogo univerzalnega Turingovega stroja. če bi npr. programirali hišni računalnik, da deluje kot univerzalni Turingov stroj, s tem strojem pa simulirali nek npr. superračunalnik, bi mikroračunalnik simuliral delovanje superračunalniku (seveda ne enako hitro).

V resnici je to v praksi mogoče narediti tudi brez uporabe Turingovega stroja in to celo dosti preprostejše. Smisel razmišljanja z uporabo Turingovega stroja je v tem, da to ekvivalenco tako lahko tudi matematično strogo dokažemo. Dokažemo lahko, da lahko univerzalni Turingov stroj in vsi današnji računalniki (če za trenutek zanemarimo omejeno velikost pomnilnika), ne glede na velike razlike med njimi, izračunajo vse funkcije iz iste množice matematičnih funkcij. Dejstvo, da obstaja ena sama množica takih funkcij, je še ena potrditev smiselnosti Church-Turingove hipoteze. Churcha in Turinga očitno ni niti najmanj motilo, da takrat, ko sta postavila to hipotezo, elektronski računalniki sploh še niso obstajali.

Gor Sistemi Motorola 68XX Turingov stroj Neodločljivi problemi

SERŠ Maribor, Strokovna gimnazija, leto: 2004/05, avtor: Mitja Ogrizek