Matematické Fórum

klaudia09 · 27. 01. 2023 12:41

Daná je úloha: Zapíšte inštrukcie pre Turingov stroj, ktorý delí binárne číslo zapísané na páske dvoma (zaokrúhli nadol).

Moje riešenie:

S0,0 -> S0,0,R
S0,1 -> S0,1,R
S0,_ -> S1,_,L

S1,0 -> S2,_,L
S1,1 -> S2,_,L
S1,_ -> S3,_,N

S2,0 -> S2,0,L
S2,1 -> S2,1,L
S2,_ -> S3,_,N

R - doprava, L- doľava, N - nehýb sa

Neviem, či je riešenie správne. V prípade, že máme binárne delenie 1 : 10 výsledok z Turingovho stroja by bol prázdny znak. Je to korektné? Ak nie prosím o opravu.

Ďakujem

check_drummer

↑ klaudia09:
Ahoj, podle mě by mělo vyjít 1:10=0 a ne prázdný znak.

Jakou myšlenku při konstrukci svého TS používáš?

klaudia09 · 27. 01. 2023 17:51

↑ check_drummer: No v stave S0 prechádzam všetky znaky vstupného binárneho čísla, až kým sa nedostanem na koniec, teda na znak _ . Vtedy prechádzam do stavu S1 a znaky začínam čítať odzadu. Znak, ktorý je posledný, prepíšem na _ , a prejdem do stavu S2. V stave S2 už iba prejdem zvyšok binárneho vstupu a nič nemením.

Jednoducho povedané iba vymažem poslednú číslicu.

V mojom prípade by teda z 1 na vstupe ostal po prepísaní strojom iba prázdny znak (prázdna páska bez 0). No myslím, že ako výsledok by mala byť 0. Či to teda vadí alebo je to v podstate to isté.

check_drummer · 27. 01. 2023 21:50

↑ klaudia09:
Podle mě to vadí. Ale asi je snadné tento případ ošetřit, a pokud nastane, tak tam napsat znak 0.

Matematické Fórum

#1 27. 01. 2023 12:41

Turingov stroj

#2 27. 01. 2023 16:14 — Editoval check_drummer (27. 01. 2023 16:15)

Re: Turingov stroj

#3 27. 01. 2023 17:51

Re: Turingov stroj

#4 27. 01. 2023 21:50

Re: Turingov stroj

Zápatí