Poniższy problem napotkałem w tym pliku PDF :
Biorąc pod uwagę TM M, czy M kiedykolwiek zapisuje niepusty symbol po uruchomieniu na pustej taśmie.
Podane rozwiązanie jest następujące:
Pozwól, aby maszyna zapisywała tylko puste miejsca symbol. Wtedy jego liczba konfiguracji w obliczeniu w wynosi q × 2, gdzie q jest liczbą stanów M; współczynnik 2 dotyczy wyborów dotyczących. kierunek ruchu głowic; nie ma żadnego czynnika na zapisany symbol, ponieważ jest on zawsze pusty. Czyli problem jest rozstrzygalny, rozstrzygany przez następującą maszynę: wejście (M, w), uruchom M na w dla q × 2 kroki; jeśli kiedykolwiek napisze inny symbol, zatrzymaj się na tak; jeśli M nigdy nie zapisuje niepustego symbolu, zatrzymaj się bez odpowiedzi
Wątpliwości:
Q1. Jak upewnić się, że wszystkie konfiguracje qx 2 zostaną zrealizowane podczas biegania qx 2 kroki na w? Niektóre konfiguracje mogą zostać powtórzone w qx 2 krokach.
Q2. Pytanie brzmi „po uruchomieniu na pusta taśma ”, ale w odpowiedzi próbowano zasymulować TM na niepustym łańcuchu w. Jaki to ma sens?
Odpowiedź
Pytanie 1: Stan może się powtarzać. Chodzi o to, że jeśli stan się powtórzy i żaden niepusty symbol nie został nawet zapisany, to wiedziałeś, że maszyna Turinga nigdy się nie zatrzyma, ponieważ koniecznie utknęła, przechodząc przez niektóre z dotychczas napotkanych stanów. Ponieważ żaden ze stanów cyklu nie spowodował, że TM zapisała niepusty symbol, TM nigdy nie zapisze niepustego symbolu.
Po $ 2q $ kroków, albo zapisano niepusty symbol i możesz odpowiedzieć „tak”, albo wszystkie zapisane symbole były puste i (co najmniej) jeden stan musiał wystąpić dwa lub więcej razy, co oznacza, że możesz odpowiedzieć „nie”.
Pytanie 2: Domyślam się, że $ w $ jest gdzieś zdefiniowane jako pusty ciąg. Jeśli TM można uruchomić dowolnym ciągiem znaków $ w $ , to odmiana powyższego rozwiązania nadal działa. Załóżmy, że nagłówek bazy TM zaczyna się na początku $ w $ . Liczba stanów zwiększa się o współczynnik co najwyżej $ 1+ | w | $ , aby uwzględnić wszystkie możliwe stany taśmy (jeśli zapisane są tylko puste symbole , to taśma zawsze zawiera jeden z sufiksów $ 1+ | w | $ z $ w $ ). Jeśli głowa może zacząć się w dowolnym miejscu, współczynnik ten wyniesie co najwyżej $ 1+ | w | ^ 2 $ .
Komentarze
- W pierwszym kwartale. Czy masz na myśli " albo napisano niepusty symbol i możesz odpowiedzieć tak … i możesz odpowiedzieć nie "? Ponieważ pytanie dotyczy ", czy M kiedykolwiek zapisuje niepusty symbol ". W II kwartale. Nie uzyskano " w liczbie stanów odpowiadającej liczbie podzbiorów pozycji w, które zostały nadpisane pustym symbolem "
- Masz rację. Poprawiłem odpowiedź. Wyjaśniłem również drugą część.