Czy jest rozstrzygalne, czy TM osiągnie jakąś pozycję na taśmie?


14

Mam te pytania ze starego egzaminu, który próbuję rozwiązać. Dla każdego problemu wejście jest kodowanie pewnej maszyny Turingowi .M

Dla liczby całkowitej i następujących trzech problemów:c>1

  1. Czy to prawda, że ​​dla każdego wejścia , M nie przechodzi przez pozycję podczas pracy na ?x|x|+cx

  2. Czy to prawda, że ​​dla każdego wejścia , M nie przechodzi przez pozycję podczas pracy na x ?xmax{|x|c,1}x

  3. Czy to prawda, że ​​dla każdego wejścia x , M nie przechodzi w pozycję (|x|+1)/c podczas pracy na x ?

Ile problemów można rozstrzygnąć?

Moim zdaniem numer problemu (1) znajduje się w coRER jeśli dobrze rozumiem, ponieważ mogę uruchomić wszystkie dane wejściowe równolegle i zatrzymać się, jeśli niektóre dane wejściowe osiągną tę pozycję, i pokazując, że to nie jest w R Mogę zredukować do tego dopełnienie Atm . Skonstruować maszynę Turinga M w następujący sposób: na wejście y sprawdzić, jeśli y to historia obliczeń, jeśli tak jest, to M prawo jazdy i nie zatrzyma się, jeśli nie jest, to zatrzyma.

W przypadku (3) uważam, że jest to rozstrzygalne, ponieważ w przypadku c2 wszystkie maszyny Turinga zawsze pozostają na pierwszej komórce paska, ponieważ dla ciągu jednego znaku może przejść przez pierwszą komórkę, więc ja muszę zasymulować wszystkie ciągi długości 1 dla kroków |Q|+1 (Czy to poprawne?) i sprawdzić, czy używam tylko pierwszej komórki we wszystkich.

Naprawdę nie wiem, co zrobić z (2).


1) Czy zakładasz jednostronną nieskończoną taśmę? 2) Co to jest Atm?
Raphael

1) Tak, 2) Problem z akceptacją.
Józef

Odpowiedzi:


9

Każda sytuacja, która pyta, czy maszyna Turinga ogranicza się do skończonej części taśmy (powiedzmy o długości ) na danym wejściu, jest rozstrzygalna.n

Argument działa w następujący sposób. Rozważ maszynę Turinga, taśmę i położenie maszyny Turinga na taśmie. Wszystkie razem mają skończoną liczbę konfiguracji. Aby być konkretnym, są tylkomożliwe konfiguracje. jest zbiorem symboli taśmy, a jest zbiorem stanów. Nadal będę używać słowa „konfiguracja”, aby opisać stan Maszyny Turinga w połączeniu ze stanem taśmy i jej pozycją na taśmie do końca tej odpowiedzi, ale to nie jest standardowe słownictwo.t=n|Γ|n|Q|ΓQ

Uruchom maszynę, śledząc wszystkie jej wcześniejsze konfiguracje. Jeśli kiedykolwiek przekroczy punkt , zwróć „tak, mija pozycję ”. W przeciwnym razie maszyna znajduje się gdzieś pomiędzy 0 a . Jeśli maszyna kiedykolwiek powtórzy konfigurację - jej stan, symbole na taśmie i jej położenie na taśmie są identyczne z poprzednimi - zwróć „nie, nigdy nie przechodzi w pozycję ”.nMnnMn

Zgodnie z zasadą pidgeonhole musi się to odbywać nie więcej niż w krokach . Wszystko powyższe jest rozstrzygalne; po co najwyżej symulowanych krokach otrzymasz odpowiedź.t+1t+1

Krótka uwaga na temat tego, dlaczego to działa: kiedy urządzenie, taśma i jej położenie na taśmie powtarzają się, musi istnieć sekwencja konfiguracji między tymi powtórzeniami. Ta sekwencja powtórzy się, prowadząc jeszcze raz do tej samej konfiguracji - maszyna znajduje się w nieskończonej pętli. Jest tak, ponieważ śledzimy każdy aspekt Maszyny Turinga; nic poza konfiguracją nie może mieć wpływu na to, co się stało. Tak więc, gdy konfiguracja się powtarza, powtórzy się ponownie, z identyczną serią konfiguracji pomiędzy.

Zatem ograniczenie taśmy do skończonej części sznurka jest rozstrzygalne. Dlatego iterując wszystkie możliwe ciągi wejściowe, problem leży w dla wszystkich trzech pytań. Być może już zdałeś sobie z tego sprawę (między twoimi pomysłami na 1 i 3 a odpowiedzią Ran G na 2 i tak wydaje się całkowicie rozwiązany), ale pomyślałem, że mimo wszystko warto to opublikować.coRE


„Jeśli maszyna kiedykolwiek powtarza konfigurację [...] zwraca„ nie ”” - to źle. Niedeterministyczna maszyna może wykonać pętlę kilka razy, a następnie przejść dalej.
Raphael

1
Mówimy tutaj o maszynach Turinga, które nie są uważane za niedeterministyczne. Jeśli byłoby to niedeterministyczne, zasymuluj wersję deterministyczną.
SamM,

Ładne wyjaśnienie. Zobacz także pierwszą wersję mojej odpowiedzi (którą koryguję, gdy zdałem sobie sprawę, że OP nie zadawała jej zbyt wiele ..)
Ran G.

@Sam: Działa w drugą stronę: jeśli nie założono inaczej, maszyna Turinga może nie być deterministyczna. Co to jest „wersja deterministyczna”? Jeśli masz na myśli całkowite rozwinięcie opcji, wówczas powtarzana konfiguracja traci znaczenie, ponieważ mogą się zdarzyć w różnych gałęziach.
Raphael

2
@Raphael standardowym sposobem na to jest wykres konfiguracji: wierzchołki są tymi samymi konfiguracjami, które Sam zdefiniował, i istnieje ukierunkowana krawędź od konfiguracji A do B, jeśli NTM może przejść z A do B w jednym kroku. Wykres jest skończony, a pytanie, czy maszyna się zatrzymuje, jest prostym pytaniem o dostępność wykresu. To pokazuje również, że jest podzbiorem D T I M E ( 2 O ( s ) )NSPACE(s)DTIME(2O(s))
Sasho Nikolov

4

(2) jest bardzo podobny do (3) i dotyczy to również tego samego rozumowania, które miałeś dla (3): zauważ, że maszyny, które w mają dziwną właściwość - nie czytają całego wejścia (nigdy nie osiągają tego ostatnie bity c ). I dotyczy to każdego wejścia.L2c

Ok, teraz rozważmy tylko dane wejściowe do długości . Dla każdego z nich są tylko dwie opcje: maszyna zapętla / zatrzymuje się bez poruszania głową lub porusza głową. Jeśli porusza głową o jakieś x (z | x |c ), to maszyna nie znajduje się w L 2 z powodu tego wejścia x . W przeciwnym razie twierdzę, że maszyna jest w L 2 . Ponieważ nigdy nie porusza głową - nie ma pojęcia, jaki jest rozmiar wejścia! oznacza to, że zachowuje się tak samo dla wszystkich danych wejściowych długości | x | > c . Dlatego też, L 2 jest rozstrzygalne.cx|x|cL2xL2|x|>cL2


Jak rozliczasz się z niedeterministycznymi maszynami?
Raphael

Nie brałem pod uwagę NTM, ale powinno być zupełnie tak samo. Dla wszystkich słów o długości do liczba konfiguracji NTM może być bez poruszania głową jest skończona. c
Ran G.

Tak, ale twój argument się załamuje. Nie można ustalić w skończonym czasie (przez prostą symulację), czy NTM opuści daną pozycję.
Raphael

@ Rafael, dlaczego nie? nie możesz symulować całego drzewa konfiguracji (głębokości ) w skończonym czasie e x p ( | x | ) ? |x|exp(|x|)
Ran G.

Po co miałaby głębia być wystarczającym? | Q | miałoby więcej sensu. Do tego czasu symulacja znalazła gałąź, w której M opuszcza pierwszą pozycję, jeśli taka istnieje. |x||Q|M
Raphael
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.