Turingův stroj

struktura a výpočty

Turingův stroj je teoretický model počítače navržený britským kryptoanalytikem a matematikem Alanem Turingem (za II. světové války byl jedním z předních kryptoanalytiků, kteří dešifrovali zprávy šifrované prostřednictvím Enigmy). Turingův stroj slouží k modelování algoritmů v teorii vyčíslitelnosti (věda zkoumající algoritmickou řešitelnost problémů).

Turing například dokázal, že neexistuje takový obecný algoritmus, který by řešil problém zastavení programu pro všechny vstupy všech programů.

Konečnost programu

I když znám zdrojový kód programu a vstup, tak nejsem vždy schopný říci, zda program poběží do nekonečna nebo se zastaví.

Definice Turingova stroje

Turingův stroj se skládá z:

  1. řídící jednotky s konečným počtem stavů
  2. konečné množiny pravidel definujících přechodovou funkci
  3. pravostranně nekonečné pásky pro vstup a zápis mezivýsledků

Turingova teze & Turingovská úplnost

  • Turingova teze: ke každému algoritmu existuje ekvivalentní Turingův stroj
  • Turingovská úplnost: turingovsky úplné jsou právě ty programovací jazyky nebo počítače, které mají stejnou výpočetní sílu jako Turingův stroj (jsou schopny spočítat vše, co Turingův stroj, tedy každý algoritmus (viz Turingova teze))

TS je sedmice: \(M = (Q, \varGamma, b, \Sigma, q_0, \delta, F)\)

  • \(Q\) je konečná množina stavů
  • \(\varGamma\) je konečná abeceda symbolů na pásce
  • \(b\) je prázdný symbol (náleží do \(\varGamma\))
  • \(\Sigma\) je konečná množina vstupních symbolů (je podmnožinou \(\varGamma\), \(b\) není součástí)
  • \(q_0\) je počáteční stav
  • \(\delta\) je přechodová funkce: \((Q / F) \times \varGamma \Rightarrow Q \times \varGamma \times (L, R) \)
    • \(L\) - posun hlavy vlevo
    • \(R\) - posun hlavy vpravo
  • \(F\) je množina koncových stavů (podmnožina \(Q\))

Konfigurace TS

  • aktuální stav q
  • počáteční úsek pásky s obsahující neprázdné symboly
  • pozice hlavy (tvořené číslem/indexem buňky n)

Formálně se jedná o uspořádanou trojici \((q, s, n)\). Kde \(q \in Q, s \in \varGamma, n \in N_0\)

Počáteční konfigurace pro vstup w je \((q_0, w, 0)\).

Výpočet

Na počátku je TS v počáteční konfiguraci a na pásce je zapsané vstupní slovo. Poté pracuje následovně:

  1. je-li aktuální stav koncovým stavem, výpočet je úspěšný
  2. hlava přečte vstupní symbol z buňky, kde se právě nachází
  3. není-li pro aktuální stav a přečtený symbol definována hodnota přechodové funkce, výpočet je neúspěšný
  4. jinak se provede instrukce popsaná hodnotou přechodové funkce (u nedeterministických strojů se vybere jeden přechod náhodně)
    • změní se stav
    • na aktuální pozici hlavy se zapíše příslušný symbol
    • hlava se posune o jednu pozici doleva nebo doprava

Příklady

Videa na pěkné příklady zde a zde.

Zdroje