Turing Recognizable => enumerable

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?

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.$\langle w_1, S_1\rangle \# \cdots \# \langle w_n, S_n\rangle$$w_i$$S_i$$M$$w_i$$n$$M$$w_i$

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\in\Sigma^*$$S$$M$$\# \langle w, S\rangle$
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\in\Sigma^*$$M$