Может ли машина Тьюринга (ТМ) решить, относится ли проблема остановки ко всем ТМ?

На этом сайте есть много вариантов вопроса о том, могут ли ТМ решить проблему остановки, будь то для всех других ТМ или определенных подмножеств. Этот вопрос несколько другой.

Он спрашивает, может ли тот факт, что проблема остановки относится ко всем ТМ, может быть решен ТМ. Я верю, что ответ отрицательный, и хочу проверить мои рассуждения.

1. Определите язык мета-остановки как язык, состоящий из ТМ, которые определяют, будет ли ТМ останавливаться.$L_{MH}$

2. $L_{MH}= \emptyset$ из-за проблемы остановки.

Таким образом, заглавный вопрос более точно сформулирован: разрешимо ли ?$L_{MH} = \emptyset$

3. Согласно теореме Райса, неразрешимо, является ли язык ре пустым.
   В обоих случаях, если равно или нет, то неразрешимо, будет ли .$L_{MH}$$L_{MH} = \emptyset$

4. Следовательно, неразрешимо, .$L_{MH} = \emptyset$

Это доказывает, что ТМ не может решить, относится ли проблема остановки ко всем ТМ.

Правильно ли мое понимание?

ОБНОВЛЕНИЕ: Я пытаюсь показать, что ТМ не может «доказать проблему остановки» для некоторого определения «доказать», которое кажется интуитивно правильным. Ниже приведена иллюстрация того, почему я считаю это правильным.

Мы можем создать TM который генерирует следующим образом. ТМ принимает кортеж . Он имитирует для итераций . Если принимает все пары, которые останавливаются, и отклоняет все остальные, то принимает . В противном случае он отклоняет если принимает неверное решение или не может остановиться.$M_{MH}$$L_{MH}$$(M_i,M_j,w_k,steps)$$M_i(M_j, w_k)$$steps$$M_i$$(M_j, w_k)$$M_{MH}$$M_i$$M_i$$M_i$

$M_{MH}$ не останавливается, потому что он должен оценивать бесконечное количество пар для каждого . Кроме того, все не смогут остановиться. не сможет принять или отклонить какой-либо как из симуляции не узнает, что все не смогут остановиться. Таким образом, язык, который он определяет, не ре и не разрешим.$M_i$$M_i$$M_{MH}$$M_i$$M_i$

$M_{MH}$ captures my intuition of what I think it means for a TM to prove the halting problem. Other suggestions, such as $M_{MH}$ rejecting all $M_i$ or outputting a known proof give $M_{MH}$ prior knowledge that the halting problem applies to all $M_i$. This cannot count as $M_{MH}$ proving something since the $M_{MH}$'s premise is the conclusion it is proving, and thus is circular.

Another viewpoint: let $\varphi$ be a formalization of the statement "$L_{MH} = \emptyset$" in ZFC; (trivially) we have:

• the set $P = \{ x \mid x \mbox{ is a valid proof of } \varphi \mbox{ in ZFC}\}$ is decidable;

• you can also build a TM $M$ that enumerates the proofs in ZFC and halts if it founds a proof of $\varphi$ or a proof of $\neg \varphi$; clearly $M$ halts;

• the set $\{ M \mid M \mbox{ decides } P \}$ is undecidable

The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO.

In other words, $\emptyset$ is decidable.

You might be confused with the fact that the language of Turing machines whose language is empty is undecidable. That is, there is no Turing machine that, on input $T$, decides whether $L(T) = \emptyset$.

You misunderstand Rice's theorem.

Rice's theorem, in this context, says that you can't decide the problem "Does T decide the empty language?".

Your problem is not about deciding whether an arbitrary Turing machine decides the empty language. Your problem is whether or not there exists an M that decides the empty language.

And such M do exist. You can do even better than that: you can actually construct such an M and provide a proof that it decides the empty language.

The general problem not being decidable does not mean you cannot solve specific instances. In fact, by the usual device of enumerating all proofs, there exists a turing machine that:

• Accepts every turing machine for which a proof exists that it decides the empty language
• Rejects every turing machine for which a proof exists that it does not decide the empty language
• Does not halt if it cannot be proven either way.

The definition about decidability from Wikipedia:

A recursive language is a formal language for which there exists a Turing machine that, when presented with any finite input string, halts and accept if the string is in the language, and halts and rejects otherwise. The Turing machine always halts: it is known as a decider and is said to decide the recursive language.

In other words, it is decidable iff there is a Turing machine that decides all input strings. It is undecidable iff for each Turing machine, it doesn't decide all input strings, which means it could decide none or some strings, but there is at least one (but practically at least infinite of them) it cannot decide.

In your case, the trivial Turing machine doesn't decide for every input $L$, whether $L = \emptyset$, but it happens to know specifically whether $L_{MH} = \emptyset$.