Mam duży problem z pewnym przeskokiem w zadaniach z maszyny turinga
Chodzi np o zadanie tego typu:
Maszyna Turinga ma mnożyć nieujemną liczbę trójkową zapisaną na taśmie razy 2. Głowica ustawiona z prawej strony.
Mój pomysł jest taki: dopóki na tasmie pojawiają się miejsca puste idź w lewo, kiedy pojawi się 0 lub 1 lub 2 cofnij się w prawo i zamień jedno miejsce puste na 0. Otrzymałem liczbę pomnożoną razy trzy. Teraz żeby otrzymac pomnożoną razy dwa odejmij liczbę początkową od tej z dopisanym zerem, tylko nie wiem jak to zrobić.
Zwracam się z prośbą o pomoc.
Maszyna Turinga
-
- Użytkownik
- Posty: 38
- Rejestracja: 4 gru 2006, o 20:39
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 8 razy
- Pomógł: 3 razy
- kwak2k
- Użytkownik
- Posty: 24
- Rejestracja: 13 paź 2008, o 09:56
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 6 razy
Maszyna Turinga
o ile dobrze zrozumialem dzialanie maszyny turinga po 1 czytaniu
to nie trzeba sie cofac tylko caly czas L , starczy ze przyjmiesz
qi = stan poprzedni bedacy przepelnieniem mnozenia przez 2 , ustawiony na 0 na starcie
i tablice
s0 qi sz qj
0 0 -> 0 0 (0*2) = 0 i 0 przepelnienia
0 1 -> 1 0 (0*2)+1 = 1 i 0 przepełnienia
1 0 -> 2 0 (1*2)+0 = 2 i 0 przepełnienia
1 1 -> 0 1 (1*2)+1 = 3 czyli (0 na wyjsciu i 1 przepełnienia)
2 0 -> 1 1 (2*2)+0 = 4 czyli (1 na wyjsciu i 1 przepełnienia)
2 1 -> 2 1 (2*2)+1 = 5 czyli (2 na wyjsciu i 1 przepełnienia)
co do 0 2 / 1 2 / 2 2 to nigdy sie nie powinny pojawic przynajmniej przy mnozeniu przez 2
maszyna powinna dzialac przyjmujac ze liczba nie konczy sie na 1 lub 2 i odrazu nie wystepuje znak konczacy
jak cos zle zrozumialem to prosze o informacje dot. bledu i z gory za niego przepraszam autora pytania
to nie trzeba sie cofac tylko caly czas L , starczy ze przyjmiesz
qi = stan poprzedni bedacy przepelnieniem mnozenia przez 2 , ustawiony na 0 na starcie
i tablice
s0 qi sz qj
0 0 -> 0 0 (0*2) = 0 i 0 przepelnienia
0 1 -> 1 0 (0*2)+1 = 1 i 0 przepełnienia
1 0 -> 2 0 (1*2)+0 = 2 i 0 przepełnienia
1 1 -> 0 1 (1*2)+1 = 3 czyli (0 na wyjsciu i 1 przepełnienia)
2 0 -> 1 1 (2*2)+0 = 4 czyli (1 na wyjsciu i 1 przepełnienia)
2 1 -> 2 1 (2*2)+1 = 5 czyli (2 na wyjsciu i 1 przepełnienia)
co do 0 2 / 1 2 / 2 2 to nigdy sie nie powinny pojawic przynajmniej przy mnozeniu przez 2
maszyna powinna dzialac przyjmujac ze liczba nie konczy sie na 1 lub 2 i odrazu nie wystepuje znak konczacy
jak cos zle zrozumialem to prosze o informacje dot. bledu i z gory za niego przepraszam autora pytania