Turingov stroj

Turingov stroj je algoritemski sistem, miselni stroj (abstrakten model), ki stvarno ne obstaja. Zamislil si ga je angleški matematik Alan Turing leta 1936, da bi z njim matematično opredelil določitev algoritma, oziroma »mehanskega postopka/programa«. Delo Turingovega stroja le oponaša človeško delo in računa po strogem predpisu. Od računalnika se razlikuje v dveh pogledih:

• razčlenitev računskega postopka je na skrajni meji zmožnosti, kar sicer podaljšuje sam postopek, vendar ga standardizira.
• spomin Turingovega stroja je neomejen.

Razredi avtomatov

V Turingovem stroju so operacije omejene na branje in zapisovanje znakov na trak ali premikanje vzdolž traku levo ali desno. Trak je označen z majhnimi kvadrati. V vsakem koraku operacije stroj zapiše ali prebere le en kvadrat, ki leži pod bralno in pisalno glavo.

Turingov stroj, ki je sposoben simulirati druge Turingove stroje, se imenuje splošni Turingov stroj ali kar splošni stroj, kakor je opisal Turing leta 1947:

Lahko se pokaže, da je moč izdelati en takšen posebni stroj, ki bi opravil delo vseh drugih. Načeloma bi lahko deloval kot model za druge stroje. Takšen posebni stroj lahko imenujemo splošni stroj.

Glej tudi

• Kitajska soba
• von Neumannov stroj
• Langtonova mravlja (preprost dvorazsežen Turingov stroj, opisljiv tudi kot celični avtomat)
• Patersonov črv (družina dvorazsežnih Turingovih strojev)
• Churcheva domneva (Church-Turingova teza) (učinkovit Turingov stroj lahko izvede poljuben račun v poljubnem jeziku)
• delovni bober (posebna vrsta Turingove stroja s praznim (eniškim) trakom)
• Minskyjev registrski stroj (posebna vrsta delovnega bobra)
• Turingov tarpon (T-popoln programski jezik)