Německý matematik David Hilbert v roce 1928 formuloval tzv. Entscheidungsproblem (rozhodovací problém). Tento problém se zabývá otázkou, zda existuje mechanický proces, kterým je možno rozhodnout o pravdivosti libovolného matematického teorému nebo výroku.
Alan Turing předpokládal, že jednoho dne budou schopny stroje rozhodnout jakýkoliv problém a tedy motivace k vytvoření Turingova stroje se stal tento Hilbertův rozhodovací problém. Turingův stroj je jeden z formálních modelů algoritmu.
Výsledkem bylo několik zjištění
1. Každý problém není řešitelný
že existují problémy, které nelze řešit algoritmicky. Neexistuje například žádný algoritmus, který by o každém polynomu s celočíselnými koeficienty dokázal rozhodnout, zda má celočíselné kořeny. Žádný algoritmus nedokáže pro každou formuli jazyka aritmetiky určit, zda je v aritmetice dokazatelná. Žádný algoritmus nedokáže o každém Turingově stroji a vstupu rozhodnout, zda se výpočet zastaví.
2. Problém, který je řešitelný nemusí být řešitelný v přijatelné době
3. Všechny programovací jazyky, které jsou Turingovsky úplné, mají stejnou vyjadřovací sílu
Programovací jazyk nazýváme Turingovsky uplný, pokud je z hlediska řešitelnosti problému ekvivalentní takzvanému Turingovu stroji. Téměř všechny bežně pouzívané programovací jazyky jsou Turingovsky úplné (a to třeba i CSS). To tedy znamená, že všechny tyto jazyky jsou vzájemně ekvivalentní z hlediska své výpočetní síly. Pokud nemůžeme problém vyřešit v jednom jazyku, pak nám přechod k jinému nikterak nepomůže.
Definice turingova stroje
Turingův stroj se skládá z řídící jednotky, neomezené čtecí pásky rozdělené do buněk a čtecí hlavy. Čtecí hlava se umí pohybovat doprava, doleva nebo posečkat na stejném místě.
Formální definice Turingův stroj je sedmice ⟨Q,Σ,G,δ,q0,B,F⟩:
Q – konečná množina stavů
Σ - konečná vstupní abeceda
G - konečná pracovní abeceda (Σ ⊂ G)
δ - zobrazení z (Q\F) × Σ do Q × Σ × {-1,0,1}
q0 ∈ Q je počáteční stav
B je prázdný symbol (B ∈ (G - Σ))
F ⊆ Q je množina koncových stavů
Deterministický a nedeterministický
Liší se v přechodové funkci. Oba jsou však stejně výkonné.
Deterministický Turingův stroj
Má následující přechodovou funkci (Q\F) × G do Q×G×{−1,0,1}.
Nedeterministický Turingův stroj
δ je zobrazení z (Q\F) × G do potenční množiny P(Q×G×{−1,0,1}).
Konfigurace
Na začátku vypočtu se čtecí hlava nachází v počátečním stavu q0, páska je vyplněna BLANK znaky.
δ(q,a) = (p, b, {-1, 0, 1})
- q je okamžitý vnitřní stav
- a je nejmenší souvislá část pásky obsahující všechny neprázdné symboly
- p je nový stav
- n je pozice čtecí hlavy. -1 je posun doprava, 0 stojí a 1 je posun doleva