Moja prosta maszyna do obróbki

Question

Próbuję zrozumieć i wdrożyć najprostszą maszynę do toczenia i chciałbym uzyskać informację zwrotną, jeśli mam sens.

Mamy nieskończoną taśmę (powiedzmy tablicę o nazwie T ze wskaźnikiem na 0 na początku) oraz tabela Instrukcja:

(S , R , W , D , N) 

S->STEP (Start at step 1) 
R->READ (0 or 1) 
W->WRITE (0 or 1) 
D->DIRECTION (0=LEFT 1=RIGHT) 
N->NEXTSTEP (Non existing step is HALT) 

moim rozumieniu jest to, że 3-state 2-symbol to najprostsza maszyna . 3-państwo nie rozumiem. 2-symbol, ponieważ używamy 0 i 1 dla READ/WRITE.

Na przykład:

(1,0,1,1,2) 
(1,1,0,1,2) 

zaczynając od kroku 1, jeśli Read jest 0 następnie {pisać 1, w prawo) else {Wpisz 0, w prawo), a następnie przejdź do kroku 2 - który nie istnieje co zatrzymuje program.

Co oznacza stan 3? Czy to urządzenie przechodzi jako maszyna tnąca? Czy możemy uprościć więcej?

Answer 1

Uważam, że koncepcja państwa jest zasadniczo taka sama jak w przypadku Finite State Machines. Jeśli sobie przypominam, potrzebny jest osobny stan zakończenia, do którego maszyna tnąca może przejść po zakończeniu programu. Co do 3 stanów, przypuszczam, że pozostałe dwa stany dotyczą odpowiednio inalizacji i wykonania.

Niestety nic z tego nie jest poprawne, ale myślałem, że mimo wszystko opowiem moje myśli, ponieważ pytanie pozostało bez odpowiedzi przez 5 godzin. Podejrzewam, że gdybyś ponownie zadał to pytanie na cstheory.stackexchange.com, możesz uzyskać lepszą/bardziej definitywną odpowiedź.

Answer 2

"Stan" w kontekście maszyn Turinga powinien zostać wyjaśniony, co jest opisywane: (i) aktualna instrukcja, lub (ii) lista symboli na taśmie wraz z aktualną instrukcją, lub (iii)) listę symboli na taśmie wraz z bieżącą instrukcją umieszczoną po lewej stronie zeskanowanego symbolu lub po prawej stronie zeskanowanego symbolu. Reference

Answer 3

Myślę, że zamieszanie może wynikać z użycia "kroków" zamiast "stanów". Możesz myśleć o stanie maszyny jako wartości, jaką ma ona w swojej pamięci (chociaż jak zauważył poprzedni plakat, niektórzy ludzie również przyjmują stan maszyny, aby uwzględnić zawartość taśmy - jednak nie sądzę, że ta definicja jest istotna na twoje pytanie). Jest możliwe, że ta zmiana terminologii może być sednem twojego zamieszania. Pozwól mi wyjaśnić, o czym myślę, że myślisz. :)

Podałeś listy pięciu liczb - na przykład (1,0, 1,2). Jak poprawnie stwierdzasz, powinno to być zinterpretowane (czytanie od lewej do prawej) jako "Jeśli maszyna jest w stanie 1, a bieżący kwadrat zawiera 0, wydrukuj 1, przesuń w prawo i przejdź do stanu 2." Jednak użycie słowa "krok" wydaje się sugerować, że po "kroku 2" musi następować "krok 3", itd., Podczas gdy w rzeczywistości maszyna Turinga może przechodzić między stanami (i oczywiście tam, może być tylko skończenie wielu możliwych stanów).

Tak, aby odpowiedzieć na Twoje pytania:

• maszyny Turinga śledzić „mówi” nie „kroki”;
• To, co opisałeś, to legalna maszyna Turinga;
• Prostsza (choć w inny sposób nieinteresująca) maszyna Turinga to taka, która zaczyna się w stanie HALT.

Edycja: Gramatyka, formatowanie i usunięcie niepotrzebnego opisu maszyn Turinga.

odpowiedzi na komentarz: Popraw mnie, jeśli mam misinterpreting komentarz, ale nie chciałem zaproponować maszynę Turinga może być w więcej niż jednym państwie na raz, tylko że liczba możliwych stanów może być dowolną skończoną liczbą. Na przykład dla maszyny z trzema stanami można oznaczyć możliwe stany A, B i C. (W podanym przykładzie oznaczono dwa możliwe stany jako "1" i "2") W dowolnym momencie, dokładnie jedna z tych wartości (stany) znajdowałaby się w pamięci urządzenia. Powiedzielibyśmy, że "maszyna jest w stanie A" lub "maszyna jest w stanie B" itd. (Twoja maszyna zaczyna działać w stanie "1" i kończy się po tym, jak wejdzie w stan "2").

Ponadto, nie jest już dla mnie jasne, co masz na myśli mówiąc o "prostszej/est" maszynie. Najmniejsza znana maszyna Universal Turing (tj. Maszyna Turinga, która może symulować inną maszynę Turinga, z odpowiednią taśmą) wymaga 2 stanów i 5 symboli (patrz the relevant Wikipedia article).

Z drugiej strony, jeśli szukasz czegoś prostszego niż maszyna Turinga o tej samej mocy obliczeniowej, może zainteresować Cię Post-Turing machines.