图灵机可以暂停和隐式接受图灵机不能处理的字符串吗？

Question

所以我遇到了一个我不确定的问题。为了好奇，我想问：

我很确定图灵机可以隐式拒绝它无法处理的字符串，但它可以做补充吗？换句话说，它可以暗含接受它不能处理的输入？我很抱歉，如果这是一个愚蠢的问题，我似乎无法找到答案。

Answer 1

这不是一个愚蠢的问题！我相信“无法处理的字符串”的含义实际上是“没有有效格式的字符串”，我认为它是“含有我们不知道的符号的字符串”。 （我要走出this presentation的幻灯片14，我只是用google搜索Turing 'implicitly reject'）。因此，如果我们使用该定义，那么我们需要简单地创建一个图灵机器，它接受一个输入，如果它包含的符号不在我们的有效集合中。

是的，还有其他可能的解释“它不能处理的字符串”，但我相当肯定这意味着这一点。它显然不能没有约束的定义，否则我们可以定义“不能处理的字符串”，例如“表示停止的程序的字符串”，并且我们已经解决了暂停问题！ （或者如果你不熟悉暂停问题，你可以替代任何NP完全问题，真的）。

我认为拒绝字符串图灵机的想法不能处理的原因是首先引入的是，使得机器可以在所有输入上被很好地定义。所以说，如果你有一个图灵机接受一个二进制数，如果它可以被3整除，但你传递的不是一个双数的输入（比如说“苹果酱”），我们仍然可以推理输出的程序。