Возможно ли, что проблема остановки разрешима для всего ввода, кроме кода машины?

Мне пришло в голову этот вопрос о проблеме остановки, и я не смог найти хорошего ответа в Интернете, задаваясь вопросом, может ли кто-нибудь помочь.

Возможно ли, что проблема остановки разрешима для любого ТМ на любом входе, если он не сам ТМ? В принципе:

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'

Это, по-видимому, разрешает противоречие. Когда мы называем парадоксальные Остановки (Halts), мы не можем ожидать последовательного поведения, но все другие вызовы Остановок (и Остановок) являются законными и разрешимыми.

Я понимаю, что это очень не интуитивно понятно. Если какой-то паттерн в битах может раскрыть поведение всех возможных программ, почему он вдруг развалится, когда ТМ и вход совпадут? Но можем ли мы математически исключить это как возможность?

И эта уменьшенная проблема остановки не будет неинтересной вообще. Даже если бы существовала какая-то значимая программа, которая взяла собственный код в качестве входных данных, ее можно было бы просто переписать, чтобы она работала на слегка отличном вводе. Конечно, это предположение делает еще менее понятным, почему может существовать остановочное решение с этим одним предупреждением, но опять же, можем ли мы действительно математически исключить эту возможность?

Спасибо за любую помощь.

Но мы можем легко обойти ваше ограничение. Предположим, что программа $G$ инвертирует биты ввода и вызывает ваш $H'$ результата, затем определите $!H$ со всеми обращенными битами (т. Е. 0 для 1 с, 1 с для 0 с). Тогда мы можем назвать свой $H'$ с $G(!H)$ , и мы вернулись к исходной задаче.

Напомним стандартное доказательство неразрешимости проблемы остановки. Предположим , что некоторая машина  решает проблему и останавливая пусть Q является машина , что на входе  ⟨ М ⟩ использует  H , чтобы определить , если M ( ⟨ М ⟩ ) останавливается , и, если да, то Q  петель; в противном случае Q  останавливается. Теперь, Q ( ⟨ Q ⟩ ) останавливается , если, и только если это не остановить.$H$$Q$$\langle M\rangle$$H$$M(\langle M\rangle)$$Q$$Q$$Q(\langle Q\rangle)$

Возможно ли, что проблема остановки разрешима для любого ТМ на любом входе, если он не сам ТМ?

Нет. Если вы измените определение проблемы остановки таким образом, доказательство все еще работает. Мы не волнует то , что происходит , когда  получает  ⟨ H ⟩ в качестве входных данных , так как противоречие приходит после того, как мы даем вход ⟨ Q ⟩ , ⟨ Q ⟩ в  H .$H$$\langle H\rangle$$\langle Q\rangle, \langle Q\rangle$$H$

Во- вторых, если вы изменяли  , чтобы обнаружить , что вход, мы могли бы получить такое же противоречие, используя любой другой машины  Q ' , что эквивалентно  Q в том смысле , что для любого входа  ш , Q ' ( ш )  привалах , если, и только если , Q ( ш )  останавливается. Их бесконечно много, и H  не может обнаружить их все, потому что неясно, эквивалентны ли две машины Тьюринга.$H$$Q'$$Q$$w$$Q'(w)$$Q(w)$$H$