Czy decydujący jest zestaw maszyn Turinga, który zatrzymuje się co najwyżej 50 kroków na wszystkich wejściach?

19

Niech . Muszę zdecydować, czy F jest rozstrzygalne, czy rekurencyjnie wyliczalne. Myślę, że jest to rozstrzygalne, ale nie wiem, jak to udowodnić.F={M:M is a TM which stops for every input in at most 50 steps}

Moje myśli

Ta część „50 kroków” natychmiast zmienia dla mnie znak R. Gdyby to było dla konkretnych danych wejściowych, byłoby rozstrzygalne. Jednak tutaj jest dla każdego wejścia. Sprawdzanie go pod kątem nieskończonych danych wejściowych sprawia, że ​​myślę, że problem dotyczy co-RE , tj. Jego dopełnienie jest dopuszczalne.

Być może mogę sprawdzić konfiguracje i zobaczyć, że wszystkie konfiguracje po 50 krokach nie prowadzą do zaakceptowania stanu - jak to zrobić?

Józef
źródło

Odpowiedzi:

21

Rozważmy bardziej ogólny problem maszyn, które zatrzymują się po co najwyżej krokach, dla niektórych . (Poniżej przedstawiono znaczne uproszczenie poprzedniej wersji tej odpowiedzi, ale w rzeczywistości jest równoważne).NN1

Jak zauważa swegi we wcześniejszej odpowiedzi, jeśli maszyna zatrzymuje się po co najwyżej N krokach, znaczące są tylko komórki 0,1,,N1 na taśmie. Następnie wystarczy zasymulować maszynę M na wszystkich ciągach wejściowych postaci xΣN , których liczba jest skończona.

  • Jeśli którakolwiek z tych symulacji nie wejdzie w stan zatrzymania przez Nthprzejście oznacza, że ​​dowolny ciąg wejściowy rozpoczynający się od x to taki, dla którego maszyna nie zatrzymuje się w ciągu pierwszych N kroków.
  • Jeśli wszystkie te symulacje zostaną zatrzymane przezprzejście, następnie zatrzymuje się w obrębie kroków na wszystkich wejściach dowolnej długości (na których podciąg długości jest wszystkim, na co kiedykolwiek działa).NthMNN
Niel de Beaudrap
źródło
I- Czy zakładam, że taki, że jego długość jest dłuższa niż jest automatycznie odrzucany? N.xN
Józef
Dlaczego nie może przeskoczyć dalej niż komórka N w ramach N kroków obliczeniowych?
Józef
@Jozef: symulacje prostu iterację wszystkich możliwych ciągów wejściowych o długości N . Możesz wykonywać kolejne ciągi znaków, ale nie nauczysz się niczego więcej, ponieważ i tak ważne są tylko pierwsze N symboli. Powodem, dla którego nie może pójść dalej niż komórki N , jest to, że maszyny Turinga (lub ich standardowa definicja i tak) przenoszą tylko jedną komórkę na krok.
Niel de Beaudrap,
Tak, rozumiem. więc masz na uwadze tylko pierwsze N ​​symboli każdego słowa, dlatego sprawdzasz wszystkie ich kombinacje. dlaczego usunąłeś opis konfiguracji?
Józef
Nadal jest widoczny, jeśli spojrzysz na poprzednie zmiany. I zmieniony go na to, ponieważ podczas gdy druga odpowiedź była może ciekawe, wiele z tego, co sprawiło, że „ciekawe” tylko służył do przesłaniać faktu, że procedura decyzyjna jest niczym więcej lub mniej niż symulowanie na wszystkich możliwych wejść o długości N . Pomyślałem, że lepiej jest zrewidować odpowiedź na coś o wiele prostszego, co w zasadzie doprowadziło do sedna tego, co sprawia, że ​​problem jest rozstrzygalny. MN
Niel de Beaudrap,
4

Jeśli zatrzymuje się w nie więcej niż 50 krokach, pozycje M, które może osiągnąć na normalnie nieskończonej taśmie, są ograniczone. Zatem taśma nieskończona może być symulowana przez taśmę skończoną. Oznacza to, że taśma może być symulowana przez automat skończony. Wynika z tego, że maszyna Turinga M, która zatrzymuje się w nie więcej niż 50 krokach, jest podobna do jakiegoś skończonego automatu M ' .MMMM

Niech będzie zbiorem stanów M , F Q zbiorem stanów akceptujących i Γ alfabetem. Następnie utworzenia zestawu stanów Q ' o M ' w następujący sposób: Q ' = { n , q , Ś , s , QMFQΓQM gdzie p jest pozycją głowicy odczytu / zapisu nad taśmą. Możemy ograniczyć pozycję { - 50 , . . . , 50 }, ponieważ liczba dozwolonych kroków obliczeniowych ogranicza liczbę osiągalnych pozycji.Q={n,q,s,p,a|n{0,...,50}qQ,sΓ,p{50,...,50},aqF}p{50,...,50}

Uwzględniając stan skończonego automatu M " to znaczy, że są w stanie Q pierwotnego automat z S na taśmie w położeniu p w którym również zapisu / odczytu głowica jest umieszczona , po n-tym kroku obliczeniowym. Stan jest przyjmowanie jednej czy z t r u E .n,q,s,p,aMqspnatrue

Przekształcenie relacji przejścia betonowej maszyny Turinga jest nieco więcej pracy, ale nie jest konieczne w pierwotnym pytaniu, ponieważ wystarczy pokazać, że przestrzeń stanu jest skończona (a zatem możemy po prostu przetestować każde wejście o długości co najwyżej 50 symbole na każdym takim automacie). Chodzi o to, aby zbudować nowy związek przejściowy, który przechodzi ze stanu do stanu n + 1 , Q ' , s ' , s " , a " w w Nn,q,s,p,an+1,q,s,p,an-tym obliczania etapu iff przejścia było w oryginalnym związku przejściowego.q,s,pq,s,p

swegi
źródło
Jak symulujesz pamięć na taśmie, tj . Możliwość ponownego odwiedzenia symboli, które już przeczytałeś, na automatach skończonych?
Niel de Beaudrap,
@NieldeBeaudrap: Wyliczasz całą przestrzeń stanu, tzn. Sprawdzasz model taśmy skończonej i automat sterujący maszyny Turinga.
swegi
1
Biorąc pod uwagę, że OP zadaje podstawowe pytania dotyczące obliczalności dla maszyn Turinga, możesz rozpakować ten szkic do czegoś pełniejszego. (Ja sam nigdy wcześniej nie słyszałem wyrażenia „sprawdzanie modelu” w kontekście obliczeniowym). W kontekście zazwyczaj przyjmowałbym, że przez „automat skończony” masz na myśli DFA lub podobny, chyba że określono inaczej, i nie jest dla mnie jasne, co odpowiadałby wkładowi DFA w taką konstrukcję. Jeśli masz na myśli wykres przedstawiający możliwe trajektorie bazy TM, to zgadzam się.
Niel de Beaudrap,
Z modelem sprawdzającym skończoną część taśmy mam zasadniczo na myśli to, co napisałeś w swojej odpowiedzi: po prostu przetestuj każde wejście o rozmiarze najwyżej 50 i sprawdź, czy osiągnięto stan akceptacji.
swegi
1
Chciałbym, żeby ludzie przestali propagować mit, że taśma maszyny Turinga musi być nieskończona. Nie ma - może być skończony, o ile jest przedłużany w razie potrzeby.
reinierpost