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?
źródło