证明一通通道机可以决定停止问题

Question

$ l = {<！m，x ！> ， mid m's text {过渡函数只能移动，} m text {halts on} x } $。我需要证明$ l $是递归/可决定的。

我想先检查$ m $的编码，并确定其过渡功能是否仅正确移动（我可以这样做吗？）。如果是这样，请尝试模拟$ x $上的$ m $ for $ | q |+1 $ step，如果停止，则$ <！m，x ！> ，，in l $ in L $，否则不是。

这个对吗？

Answer 1

我认为$ q $是$ m $的状态集。如果是这样，此运行时界限没有多大意义。特别是，具有三个状态的图灵机可以移至输入末尾，并检查$ x $是否是偶数号码；显然，等待三个步骤还不够。

下一个问题是是否在那里 是 可以在停止一通机器的运行时进行计算绑定。不幸的是，没有：$ m $在任意步骤之后可能是无确定性的，并且停止了。

因此，我们在模拟（可计算）时确定$ m $，并寻找所有路径的界限。现在我们到达某个地方：消耗了输入后，有两种情况。 $ m $ halts或它进入循环。由于它只能向右移动（进入空胶带），因此可以检测到此类循环。

将东西放在一起，我们模拟了$ M $的决定。我们运行每个分支机构，直到消耗$ x $，然后再为另一个$ | q | cdot | sigma_t | $ step，$ q $ $ q $ the natess和$ sigma_t $ $ m $ $ m $的磁带字母。此时，$ m $已停止或循环（在此分支中），我们通过第二次发生的两对当前状态和磁带符号检测到。我们只需要检查有限的许多分支，直到可计算的界限，因此$ l $是递归的。

---

1. $ m $如果不允许头部移动，则可能已经在这里循环，但也可以检测到。