Turingův stroj je pojem z informatiky. Nejedná se o fyzický stroj, ale o formální model výpočtu — systém pravidel, stavů a přechodů, který poprvé v roce 1936 představil anglický matematik a počítačový vědec Alan Turing. Turingův stroj slouží především k modelování a analýze výpočetních procesů: používá se při rozhodování ve formálních jazycích a při studiu výpočtu matematických funkcí. Turingovy stroje patří mezi základní formální modely teorie výpočtů a teoretické informatiky.

 

Definice a základní složky

Formálně se Turingův stroj většinou popisuje sedmičlenným uspořádáním (Q, Σ, Γ, δ, q0, q_accept, q_reject), kde:

  • Q je konečná množina stavů stroje.
  • Σ je vstupní abeceda (znaky, které mohou být na pásce jako vstup).
  • Γ je pásková abeceda (obsahuje Σ a navíc speciální symboly, např. prázdný symbol).
  • δ je přechodová funkce (nebo relace) určující, jak se stroj chová: podle aktuálního stavu a znaku pod čtecí/zapisovací hlavou určí nový znak, nový stav a pohyb hlavy (vlevo/vpravo).
  • q0 je počáteční stav.
  • q_accept a q_reject jsou akceptační (přijímací) a odmítací (zamítací) stavy ukončení výpočtu.

Páska slouží jako nekonečná (obvykle oboustranně nebo jednostranně nekonečná) paměť rozdělená na buňky; hlava čte a zapisuje symboly a může se posouvat. Stroj postupuje krok po kroku podle přechodové funkce.

Typy Turingových strojů

  • Deterministický Turingův stroj (DTM) — pro daný stav a znak existuje nejvýše jeden přechod.
  • Nedeterministický Turingův stroj (NDTM) — pro stav a znak může existovat více možných přechodů; NDTM „uspěje“, pokud existuje alespoň jedna cesta vedoucí k přijímacímu stavu.
  • Vícepáskové stroje — mají více pásek a hlav; lze je simulovat jednopáskovým strojem (s polynomální režijní náročností).
  • Univerzální Turingův stroj (UTM) — stroj, který přijímá popis jiného Turingova stroje a jeho vstupu a simuluje tento stroj; klíčový pro myšlenku programovatelných počítačů.

Výpočetní schopnosti a omezení

Turingův stroj je velmi silný model: dokáže vyjádřit jakýkoli algoritmicky vyčíslitelný výpočet. Důležité pojmy jsou:

  • Rozhodnutelné (decidable) jazyky: jazyky, pro které existuje Turingův stroj, který vždy zastaví a buď akceptuje (pokud vstup patří do jazyka), nebo zamítne (pokud nepatří).
  • Rozpoznatelné (recursively enumerable) jazyky: jazyky, pro které existuje Turingův stroj, který akceptuje každé vstupní slovo patřící do jazyka; pro slova, která do jazyka nepatří, může stroj buď zastavit a zamítnout, nebo běžet donekonečna.
  • Neřešitelné problémy: neexistují Turingovy stroje pro některé úlohy; typickým příkladem je Halting problem (problém zastavení), který je nedůkazně rozhodnutelný.

Church-Turingova teze

Church-Turingova teze říká, že všechny intuitivně efektivní (algoritmicky proveditelné) postupy lze realizovat Turingovým strojem. Není to matematicky dokazatelné tvrzení, ale hypotéza podložená shodou více formálních definic výpočtu (lambda kalkul, rekurzivní funkce, Turingovy stroje) a praktickými zkušenostmi s programováním a architekturou počítačů.

Význam v informatice

  • Teoretická analýza: Turingův stroj je základní nástroj pro studium rozhodnutelnosti, složitosti a výpočetních tříd (P, NP, PSPACE, atd.).
  • Historie a koncepce počítačů: myšlenka univerzálního stroje předznamenala pojem programovatelného počítače.
  • Formalizace algoritmů: poskytuje přesný matematický model pro to, co znamená „algoritmus“ či „výpočet“.

Komplexita a efektivita

I když Turingův stroj modeluje, co je vypočítatelné, studium časové a prostorové náročnosti (time/space complexity) na Turingových strojích vede k základním třídám složitosti (např. P, NP, EXP, PSPACE). Mnoho výsledků teorie složitosti vychází právě z analýzy chování Turingových strojů.

Příklady a ilustrační popis

Jednoduchý příklad úlohy: rozhodnout jazyk {a^n b^n | n ≥ 0} (řetězce, které mají nkrát 'a' následovaných nkrát 'b'). Turingův stroj může postupně párovat první nepárované 'a' s první odpovídající 'b' (označí je speciálním symbolem), opakovat až do vyčerpání a potom zkontrolovat, zda žádné nepárované znaky nezůstaly. Takový stroj demonstruje, jak pomocí jednoduchých pravidel a stavů lze realizovat kontrolu struktury řetězců.

Varianty a rozšíření

  • Bezkonečná páska obou stran nebo pouze vpravo; více hlav; vícepáskové stroje.
  • Probabilistické, kvantové a relativistické varianty Turingových strojů pro modelování náhodných či kvantových výpočtů.

Závěr

Turingův stroj je jednoduchý, ale velmi silný formální model, který poskytuje pevný teoretický základ pro pochopení omezení a možností výpočtů. Je centrální pro teorii výpočetní složitosti, rozhodnutelnosti a pro historické pojetí programovatelných počítačů. I když reálné počítače používají jiné konstrukce a optimalizace, principy vyjádřené Turingovým strojem jsou stále relevantní pro porozumění tomu, co lze (a co nelze) algoritmicky vyřešit.