Czy to możliwe, że problem zatrzymania można rozwiązać dla wszystkich danych wejściowych oprócz kodu maszyny?

To pytanie przyszło mi do głowy z powodu problemu z zatrzymaniem i nie mogłem znaleźć dobrej odpowiedzi online, zastanawiając się, czy ktoś może pomóc.

Czy jest możliwe, że problem zatrzymania jest rozstrzygalny dla dowolnej TM na dowolnym wejściu, o ile wejście nie jest samą TM? Gruntownie:

Halts(TM, I)
    IF TM == I:
        Undecidable, return a random result/throw an exception, whatever
    ELSE:
        Solve the problem

Halts'(X)
    IF Halts(X, X):
        Loop infinitely
    ELSE:
        Print 'done'

To pozornie rozwiązuje sprzeczność. Kiedy nazywamy paradoksalne „Halts”, nie możemy spodziewać się spójnego zachowania, ale wszystkie inne wezwania do Halts (i „Halts”) są uzasadnione i możliwe do rozwiązania.

Rozumiem, że jest to bardzo nieintuicyjne. Jeśli jakiś wzorzec w bitach może ujawnić zachowanie wszystkich możliwych programów, dlaczego nagle rozpadłby się, gdy TM i wejście pasowałyby do siebie? Ale czy możemy matematycznie wyeliminować to jako możliwość?

Ten zredukowany problem zatrzymania nie byłby wcale nieciekawy. Nawet jeśli istniał jakiś znaczący program, który pobierał własny kod jako dane wejściowe, można go w prosty sposób przepisać, aby działał na nieco innych danych wejściowych. Oczywiście ta sugestia sprawia, że ​​jest jeszcze mniej zrozumiałe, dlaczego istniało rozwiązanie wstrzymujące z tym jednym zastrzeżeniem, ale ponownie, czy naprawdę możemy matematycznie wyeliminować tę możliwość?

Dziękuję za wszelką pomoc.

Ale możemy łatwo ominąć twoje ograniczenia. Załóżmy, że program odwraca bity wejścia i wywołuje na wyniku, a następnie zdefiniuj z odwróconymi wszystkimi bitami (tj. 0 dla 1s, 1s dla 0s). Następnie możemy wywołać twoje pomocą i wrócimy do pierwotnego problemu.$G$$H'$$!H$$H'$$G(!H)$

Przypomnijmy standardowy dowód nierozstrzygalności problemu zatrzymania. Załóżmy, że jakaś maszyna  decyduje o problemie zatrzymania i niech będzie maszyną, która na wejściu  używa  do ustalenia, czy zatrzymuje się, a jeśli tak, to  pętle ; w przeciwnym razie  zatrzymuje się. Teraz zatrzymuje się tylko wtedy, gdy się nie zatrzymuje.$H$$Q$$\langle M\rangle$$H$$M(\langle M\rangle)$$Q$$Q$$Q(\langle Q\rangle)$

Czy jest możliwe, że problem zatrzymania jest rozstrzygalny dla dowolnej TM na dowolnym wejściu, o ile wejście nie jest samą TM?

Nie. Jeśli zmienisz w ten sposób definicję problemu zatrzymania, dowód nadal działa. Nie obchodzi mnie, co się dzieje, gdy  otrzymuje  jako wejście ponieważ sprzeczność przychodzi po dajemy wejście do  .$H$$\langle H\rangle$$\langle Q\rangle, \langle Q\rangle$$H$

Po drugie, jeśli zmodyfikowałeś  celu wykrycia tego wejścia, moglibyśmy uzyskać tę samą sprzeczność, używając dowolnej innej maszyny  która jest równoważna  w tym sensie, że dla każdego wejścia  ,  zatrzymuje się wtedy i tylko wtedy, gdy ,  zatrzymuje się. Jest ich nieskończenie wiele i  nie może ich wszystkich wykryć, ponieważ nie można rozstrzygnąć, czy dwie maszyny Turinga są równoważne.$H$$Q'$$Q$$w$$Q'(w)$$Q(w)$$H$