Rešitev: Turingov stroj Odštej

Iz MaFiRaWiki

Naloga: Turingov stroj Odštej

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

a > = b:

S 1 D S

S 0 D A

A 1 0 B

B 0 L B

B 1 0 S

(A10B)

A P L C

C 0 P A

C 1 L C

Stroj začne v stanju S in se zapelje desno do 0, ki loči števili. Nato v stanjih A in B izmenično briše po eno 1 v vsakem številu, vedno najprej pri številu, ki ga odštevamo. Ko pride do praznega prostora, se prestavi v stanje C, v katerem se zapelje levo in konča, pri tem pa sproti pobriše vse ničle. Če je b > a, potem vrne rezultat 0 in konča v stanju B namesto C.


a,b poljubni naravni št.:

S 1 P A

A P D B

B 1 D B

B 0 1 C

C 1 D F

F 1 0 E

E 0 L E

E 1 0 F

F 0 D F

F 1 0 E

F P L Z

E P 1 G

G 1 D G

G 0 1 H

H 1 D K

K 0 D K

K 1 0 L

L 0 L L

L 1 D G

K P L Z

Z 0 P W

Z 1 L Z

Z P O W

W P L Z

W 0 L W

Stroj v stanjih S, A in B na začeteku traku ustvari prazno mesto, zbrisano enico pa prestavi na mesto, kjer je sprva 0 ločevala števili. V stanju C se prestavi na prvo 1 drugega števila. V stanjih F in E izmenično zamenjuje 1 z 0 pri obeh številih. Če je a > = b v stanju F pride do praznega mesta in se prestavi v stanje Z. Prek stanj Z in W se vrne na začetek traku, vmes pa 0 spreminja v P. Prazen prostor na začetku traku v stanju Z spremeni v 0, ki predstavlja pozitiven predznak, in konča. Če je b > a, pride v stanju E do praznega mesta na začetku traku in ga spremeni v 1, ki pomeni -. Nato v stanju G doda še eno 1, v stanju H pa se prestavi desno na 0. V stanjih K, L, G in H odvzema 1 od drugega števila in jih dodaja razliki. Ko v stanju K naleti na prazno mesto se prek stanj Z in W vrne na začetek in konča, sproti pa pobriše 0. Prva oznaka določa predznak: 0= + , 1=, ostale 1 pa predstavljajo absolutno vrednost.

Osebna orodja