Turing Recognizable => enumerable

10

Dostaję dowód przejścia z modułu wyliczającego do maszyny Turinga (kontynuuj działanie modułu wyliczającego i zobacz, czy pasuje on do danych wejściowych), ale nie widzę, jak działa inny sposób.

Zgodnie z moimi notatkami i książką (Wprowadzenie do teorii obliczeń - Sipser), aby pobrać moduł wyliczający Turinga z maszyny Turinga, w zasadzie piszemy wszystkie kombinacje alfabetu. Następnie uruchom TM dla tego wejścia, jeśli zaakceptuje wydrukowanie, zamień na nowy ciąg powtarzaj ad infinitum.

Problem, który mam, z pewnością wymaga rozstrzygnięcia języka. W przeciwnym razie może utknąć na trzecim słowie w nieskończonej pętli skazanej na to, że nigdy nie zaakceptuje ani nie odrzuci, a na pewno nigdy nie wydrukuje całego języka.

czego mi brakuje?

T. Kiley
źródło

Odpowiedzi:

9

Brakuje sposobu uruchamiania maszyny Turinga na ciągach znaków, aby uzyskać moduł wyliczający. Zamiast generować każdy ciąg, uruchom M , a następnie wyślij ten ciąg, jeśli M zaakceptuje - co, jak zidentyfikowałeś, nie zadziała - robisz coś w następujący sposób, który przyjmuje strategię symulowania wielu wystąpień M na różnych ciągach „w równolegle".M.M.M.M.

Przyjmuje się, że taśma ma zawartość , w którym W i jest nieco słowo pod uwagę i Ś I jest obecny stan M operacyjny na wag I . Oznacza to, że n kopii M jest symulowanych. w i jest przechowywane, więc wiemy, jakie było oryginalne wejście.w1,S.1##wn,S.nwjaS.jaM.wjanM.wja

Teraz uruchom następującą pętlę

  1. Na koniec zapisu taśmy następny ciąg od , wraz z początkowej konfiguracji S o M , czyli zapisu # wag , S .wΣS.M.#w,S.
  2. Symuluj każdą kopię litery na taśmie dla jednego kroku. (Prawdopodobnie użyj innej taśmy).M.
  3. Jeśli któryś z wejdzie w stan akceptacji, umieść odpowiedni ciąg na taśmie wyjściowej. Usuń to wystąpienie litery M z taśmy.M.M.
  4. Jeśli któryś z wejdzie w stan odrzucenia, usuń to wystąpienie M z taśmy.M.M.
  5. Idź do kroku 1.

wΣM.

Dave Clarke
źródło
4
alias „gołębi ogon”.
Kaveh