非确定型TM等价确定型TM定理：第三带数字来源咨询

嘿，我来帮你把第三带的数字来源讲明白！其实这背后是用确定型TM的枚举策略来模拟非确定型TM的所有可能分支，第三带的数字就是用来标记「我现在要模拟哪一条具体的非确定路径」的编码。

具体来说，你可以这么理解：

• 首先，非确定型TM在每一步计算时，可能有多个可选的转移动作（比如不同的纸带改写、读写头移动、状态跳转）。我们可以给每个「当前状态+当前读入符号」组合下的所有转移选项编个号，比如从1到n（n是当前可选转移的数量）。
• 第三带上的数字，本质是非确定选择序列的编码。比如：
  • 数字「1」代表只走第一步的第1种转移；
  • 数字「2」代表只走第一步的第2种转移；
  • 数字「11」代表第一步选第1种、第二步也选第1种的路径；
  • 数字「12」代表第一步选第1种、第二步选第2种的路径；
    简单说就是把每一步的选择编号按顺序拼起来，或者用自然数的顺序来枚举所有可能的有限长度选择序列（比如用字典序把所有路径映射到自然数）。
• 确定型TM的工作逻辑是：先在第三带上写下数字1，模拟这条路径；如果这条路径走到拒绝或者进入循环，就把第三带的数字换成下一个自然数，模拟下一条路径，直到找到一条能接受输入的路径，或者枚举完所有可能路径（如果都不接受就拒绝）。

举个更具体的例子：假设非确定TM在状态q0读入字符a时有3种转移选项：1. 写b、右移、到q1；2. 写a、左移、到q2；3. 写c、不动、到q3。那第三带如果是数字「3」，就告诉确定TM：现在模拟第一步选第3种转移的路径；如果是「21」，就模拟第一步选2、第二步选1的路径。

这样第三带的数字就相当于给所有可能的非确定路径分配了一个唯一的“身份证号”，确定型TM靠逐个遍历这些“身份证号”，就能覆盖非确定TM的所有可能计算分支啦。

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