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.
Kombinacijska logikaStroj s končnim stanjemPotisni avtomatTuringov strojTeorija avtomatov
Razredi avtomatov (Klikni na vsako plast, da prideš na članek o tem)

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 uredi

Zunanje povezave uredi