Turingov stroj

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Turingov stroj je algoritemski sistem, miselni stroj (abstrakten model), ki stvarno ne obstaja. Zamislil si ga je angleški matematik Alan Mathison 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.

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 | uredi kodo]

Zunanje povezave[uredi | uredi kodo]