Pytanie dotyczące maszyny Turinga w stanie bezużytecznym

OK, oto pytanie z poprzedniego testu w mojej klasie teorii obliczeń:

Stan bezużyteczny w bazie TM to taki, który nigdy nie jest wprowadzany w żadnym ciągu wejściowym. Niech Udowodnij, że U S E L E S S T M jest nierozstrzygalny.

$$\mathrm{USELESS}_{\mathrm{TM}} = \{\langle M, q \rangle \mid q \text{ is a useless state in }M\}.$$ $\mathrm{USELESS}_{\mathrm{TM}}$

Myślę, że mam odpowiedź, ale nie jestem pewien, czy jest poprawna. Uwzględni to w sekcji odpowiedzi.

Można to wyraźnie zredukować od problemu zatrzymania. Jeśli maszyna nie zatrzymuje się na wejściu x, wówczas dowolny stan końcowy jest „bezużyteczny”. Biorąc pod uwagę wejście M , x dla problemu zatrzymania, łatwo jest zbudować M x, który zatrzymuje się na każdym wejściu (a zatem jego stan końcowy nie jest bezużyteczny) wtedy i tylko wtedy, gdy M zatrzymuje się na x . W ten sposób możesz zdecydować o problemie zatrzymania, jeśli możesz zdecydować U S E L E S S T M , co daje sprzeczność.$M$$x$$M,x$$M_x$$M$$x$$\mathrm{USELESS}_{\mathrm{TM}}$

Dla celów tego dowodu zakładamy, że jest rozstrzygalne wyświetlanie sprzeczność.$\mathrm{USELESS}_{\mathrm{TM}}$

$R$

• $M$$P$$M$
• $P$
• Od stanu początkowego rozpocznij pierwsze wyszukiwanie wzdłuż każdej krawędzi wychodzącej, zaznaczając każdy nieoznaczony węzeł.
• $q$

$S$

1. $R$
2. $q$$R$
3. $R$$R$

$R$$\mathrm{USELESS}_{\mathrm{TM}}$$S$$A_{\mathrm{TM}}$$A_{\mathrm{TM}}$$\mathrm{USELESS}_{\mathrm{TM}}$