Naloga: Turingov stroj Seštej/Rešitev

Iz MaFiRaWiki

Predpostavka: vhod je oblike 11...11011...11PP... (števili sta predstavljeni z enicami in ločeni z ničlo, P pomeni prazno mesto).

S 1 D S

S 0 1 A

A 1 D S

S P L B

B 1 P C

C P L C

C 1 L C

Stroj začne v stanju S in se premika desno do ničle med številoma, ki ju je treba sešteti. Tam 0 nadomesti z 1 in se premakne v stanje A. Nato se spet prestavi nazaj v stanje S in gre desno dokler ne pride do praznega mesta, kjer preide v stanje B. V tem stanju gre za eno mesto v levo in zadnjo 1 drugega števila zbriše ter pusti prazno mesto. Nato se prek stanja C zapelje levo do konca traku in konča.

Osebna orodja