Turingův stroj navrhl Alan Turing v roce 1936 jako prostředek pro studium algoritmů. Jde o abstraktní systém. Můžeme si jej však představit jako reálné zařízení tvořené třemi základními částmi, a to

1. řídící jednotkou,
2. hlavou pro čtení a zápis,
3. doprava nekonečnou páskou s políčky pro zpracovávané symboly.

Zajímavé je, že náhražku Turingova stroje s konečnou páskou, si někteří nadšenci sestro­jují dokonce i ze dřeva. Viz Richard Ridel

Řídící jednotka je konečný automat. Symboly nějaké abecedy čte z nekonečné pásky snímací hlava, která je na pásku opět zapisuje. Páska se může pohybovat vždy o jedno políčko oběma směry s výjimkou prvního políčka zleva. V každém kroku přečte hlava jeden symbol z pásky, konečný automat změní svůj stav, hlavaᛏ zapíše symbol na pole pásky, ze kterého četla a páska se posune o jedno pole vlevo nebo vpravo.ᛏ

Na pásku Turingova stroje zapíšeme konečný počet symbolů vstupní abecedy, na ostatních polích zůstanou prázdné symboly „ “, které v definici označíme například Δ, konečný automat nastavíme do počátečního stavu, hlavu umístíme nad počáteční symbol a stroj spustíme.ᛏ

Turingův stroj definujeme jako uspořádanou pětici

kde symbol L z množiny {L, R} označuje, že se páska posune vlevo, symbol R znamená, že se páska posune doprava.ᛏ

Přechodová funkce δ přiřazuje některým dvojicím (x, u) trojici (x′, u′, d), kde x ∈ X − F je současný stav automatu, u ∈ U je symbol přečtený z pásky, x′ je nová hodnota stavu, u′ ∈ U je nová hodnota symbolu, kterým bude nahrazen na pásce symbol u a d ∈ {L, R} určuje směr posunu hlavy. Pro stavy x ∈ F není přechodová funkce δ definována, výpočet končí a stroj se v koncovém stavu zastaví. Avšak i pro některé stavy x ∈ X − F a vstupní symboly u ∈ U nemusí bát přechodová funkce definována. Také v tomto případě výpočet končí a stroj se zastaví ve stavu x, který nepatří do množiny F. Podobně je výpočet ukončen a stroj se zastaví, jestliže je hlava nad prvním symbolem pásky zleva a je požadováno další posunutí pásky vpravo (tj. hlavy vlevo).ᛏ

Abychom mohli jednoduše sledovat činnost Turingova stroje, zavedeme označení zahrnující situaci na pásce, polohu hlavy a stav automatu. Konfigurace Turingova stroje je výraz tvaru αxβ, který znamená, že na pásce je v daném okamžiku zapsán řetěz αβ, kde α, β ∈ U*, automat je ve stavu x ∈ X a hlava stojí nad prvním symbolem zleva řetězu β. Prázdné symboly Δ vlevo od řetězu α a vpravo od řetězu β neuvažujeme. Nejpřehlednější ovšem je je napsat stav nad nebo pod symbol, na kterém se nachází páska.ᛏ

Ukázka výpočtu pomocí Turingova strojeᛏ

Tento Turingův stroj má pouhé dva stavy a pracuje na pásce, na které mohou být zapsány znaky 0, 1 a prázdný znak. Stavy jsou označeny znaky A a B. Prázdný znak je v tabulce řídícího automatu bez označení. V tabulce situací (konfigurací stroje) na pásce je zadáno výchozí, slovo, počáteční umístění hlavy a počáteční stav. Tím je zadán postup výpočtu Turingova stroje. Můžeme jej sledovat až k jeho zastavení. Po zastavení na pásce zůstane slovo, které je řešením požadovaného zadání.

Zadání Turingova stroje pomocí tabulky a popis situací na pásce během činnosti. Popisy situací jsou dva pro dvě různé varianty zadání.

Slovo v zadání znamená číslo ve dvojkové soustavě a popsaný Turingův stroj k němu při každém spuštění přičte číslo 1 a zastaví se. Zastavení u levého sloupce situací obecně nemusí nastat nad první jedničkou, jak se stalo shodou okolností v našem případě. V pravém sloupci pod sebe na prázdný znak před první číslici na pásce jedničku zapíše vždy.