Klasický Turingův stroj

Motivací pro Turingův stroj se stal v roce 1900 tzv. Entscheidungsproblem (rozhodovací problém). V něm německý matematik David Hilbert formuloval problém, ve kterém se ptal, zda existuje mechanický proces, kterým je možno rozhodnout o pravdivosti libovolného matematického teorému nebo výroku. Hilbert se chtěl přesvědčit, zda je například možné vyjádřit kroky matematického důkazu spíše posloupností symbolů, než složitým matematickým aparátem. Toho se chopil Turing a navrhl stroj, který měl simulovat postup matematika při vytváření důkazu. Takový stroj měl několik základních vlastností:

• musel nahradit složitou symboliku matematických kroků. V takovém případě šlo každou konečnou množinu symbolů nahradit pouze dvěma symboly (jako je 0 a 1) a prázdnou mezerou, která by oba symboly oddělovala.
• podobně jako si matematik zapisuje poznámky na papír, má Turingův stroj k zápisu nekonečnou pásku skládající se z buněk, do/ze kterých se symbol zapisuje/čte.
• nad touto páskou je možné provádět za pomocí čtecí hlavy operace čtení, zápisu a posunu pásky (read, write, shl, shr).
• protože je možné symboly číst, zapisovat nebo se posunovat po pásce, je pro Turingův stroj důležitý vnitřní stav, ve kterém operaci čtení provádíme (čtený symbol a stav tak určují další akci a přechod do dalšího stavu).

Protože se chování tohoto stroje vyvíjí podle tabulky přechodů, můžeme říci, že každý následující stav lze jednoznačně určit na základě čteného symbolu a aktuálního stavu. Jeho chování je proto deterministické.

Obrázek: Deterministický Turingův stroj

Výpočet začíná tak, že jsou na pásce uložena počáteční data (pokud jsou nějaká) a vlastní kód programu. Hlava je pak uvedena do stavu, který odpovídá načtení kódu programu a stroj tak započne výpočet, přechází mezi stavy a po skončení většinou zapíše výsledek. Vidíme, že takto se chovající model by se dal velmi dobře přirovnat k funkci dnešních počítačů. Přestože moderní technologie nevídaně od 30.let pokročily, Turingův model můžeme k popisu chování počítačů použít bez úprav i dnes. S trochou nadsázky se dá říci, že principiálně se supervýkonný ASCI Red od Intelu rovná jakémukoliv stolnímu počítači. Pomocí Turingova stroje pak bylo dokázáno, že odpověď na počáteční Hilbertovu otázku je záporná. Neexistuje tak mechanický stroj, který by rozhodl pravdivost nebo nepravdivost libovolného matematického výroku.