固定图灵机和固定输入的停止问题

Question

众所周知，即使我们修复 turing machine $ m $ 或输入 $ w $ 。

如果我们修复了机器和输入？IE，对于每个固定的图灵机 $ m_0 $ 和每个固定输入 $ w_0 $ 跨越类=“math-container”> $ m_0 $ 将停止在 $ w_0 $ 作为输入？

Answer 1

众所周知，即使我们修复 turing machine $ m $ 或输入 $ w $ 。

您必须更加谨慎地了解此声明。对于任何固定的图定机器 $ m $ 暂停问题 $ \ text {halt} _m $ （决定输入 $ w $ 如果 $ m $ 停止 $ w $ ）是不可判定的。例如，如果 $ m $ 是一台始终停止的机器，我们可以轻松地决定 $ \ text {halt} _m $ 仅通过输出“是”。

你可能意味着说是以下事实，这是真的：

1. 存在一个图定机 $ m $ ，使得问题 $ \ text {halt} _m $ （决定输入 $ w $ 如果 $ m $ 停止 $ w $ ）是不可行的。

2. 对于所有字样 $ w $ ，问题 $ \ text { halt} _w $ （决定输入 $ m $ 如果 $ m $ 停止< SPAN Class=“math-container”> $ w $ ）是不可判定的。

特别是事实上1，我们可以使用 $ m $ 是通用图灵机。

如果我们修复了机器和输入？ IE，对于每个固定的图灵机 $ m_0 $ 和每个固定输入 $ w_0 $ 跨越类=“math-container”> $ m_0 $ 将停止在 $ w_0 $ 作为输入？

是的，问题变得庞大可判定。定义语言 $ \ text {halt} _ {m_0，w_0} $ 是决定 $ m_0 $ 停止 $ w_0 $ 。但请注意，此问题不再具有答案取决于的任何输入，作为答案可能取决于的内容（ $ m_0 $ 和 $ w_0 $ ）现在是固定的，即语言定义的一部分，而不是输入的一部分。这意味着答案只是“是”或“否”。因此，我们可以通过使用总是说“是”的程序来实现这一问题，或者是总是说“否”的程序。

这是一个常见的脱钩性缺陷：询问问题是否可解除，当可能输入的数量是无限的时，它只是有用的。如果只有有限可能的输入，那么所有问题都变得可判定。 您已经询问一个只有1个可能的输入（空输入）的问题是否可解释，并且答案始终是肯定。