不可判定场景下带y、n双停机状态的Turing machine解析

要回答这个问题，首先得记住图灵机作为语言判定器的硬性要求：
对任意有限长度的输入串，机器必须在有限步内停机，且满足：

• 输入属于待判定语言L时，只能停在接受状态y
• 输入不属于L时，只能停在拒绝状态n
  只要有任意一个输入不满足这个要求（比如死循环不停机、同一个输入既能到y也能到n），这个图灵机就不能判定任何语言。题目要的就是这种“长着判定器的样子（有y、n两个停机态），但根本当不了判定器”的例子。

先直接答你最困惑的两个问题：

1. 磁头移动方向：这个机器只有一种磁头动作，就是右移，没有左移规则。
2. 机器类型：这是非确定型图灵机（NTM），同一状态下读取同一个符号时，存在多个可选择的转移，不是确定型机器。

具体转移规则 #

机器一共只有3个状态：初始状态q0，停机状态y、n，转移规则如下（非确定选择，只要匹配当前读取符号就能选）：

• 规则1：q0状态下读到任意符号（0、1、空白符⊔），可以选择写回原符号，磁头右移一格，保持q0状态
• 规则2：q0状态下读到任意符号（0、1、空白符⊔），可以选择直接进入n状态停机，不修改带、不移动磁头
• 规则3：q0状态下读到空白符⊔，可以选择直接进入y状态停机，不修改带、不移动磁头

运行行为模拟 #

不管输入什么长度的串w，运行逻辑都非常简单：

• 初始时磁头停在输入串的第一个字符位置，带面上除了输入串之外全是空白符
• 只要磁头还在输入串的0/1字符上，每一步你都可以选：要么直接停n，要么右移一格看下一个字符
• 当磁头移过整个输入串、碰到右侧的空白符时，你可以选：直接停n、继续右移（还是空白区）、直接停y
• 所有可能的计算路径都是有限的：哪怕一直选右移，也随时可以停n，碰到空白随时可以停y，不存在死循环。

它完全符合题目的要求：

1. 确实有y、n两个独立的停机状态，外观上和判定器的结构一致
2. 它永远不可能判定任何语言：对所有可能的输入（包括空串），都同时存在停到y和停到n的路径：
   • 想停n非常简单：第一步就选规则2，不管输入是什么直接停n
   • 想停y也非常简单：一直选规则1右移，走完整个输入碰到空白后选规则3，直接停y
     你找不到任何一个输入是“只会停y不会停n”或者“只会停n不会停y”的，根本没法定义它接受什么串、拒绝什么串，自然不可能成为任何语言的判定器。

内容的提问来源于stack exchange，提问作者aborted