#1 27. 01. 2023 12:41
Turingov stroj
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
Offline
#2 27. 01. 2023 16:14 — Editoval check_drummer (27. 01. 2023 16:15)
- check_drummer
- Příspěvky: 5578
- Reputace: 106
Re: Turingov stroj
↑ 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áš?
"Máte úhel beta." "No to nemám."
Offline
#3 27. 01. 2023 17:51
Re: Turingov stroj
↑ 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é.
Offline
#4 27. 01. 2023 21:50
- check_drummer
- Příspěvky: 5578
- Reputace: 106
Re: Turingov stroj
↑ klaudia09:
Podle mě to vadí. Ale asi je snadné tento případ ošetřit, a pokud nastane, tak tam napsat znak 0.
"Máte úhel beta." "No to nemám."
Offline