递归集或不递归集

Question

我正在试着解决大学里的一个问题，但我不知道如何解决它。有没有人可以帮助我说，我怎样才能证明下面提到的两种语言是可判定的或不可判定的？

在输入w上，图灵机M从不向左移动读/写头，其中w∈{0，1}∗L1:= M∈{0，1}∗。

在输入w上，图灵机M在每个步骤中移动读/写头，其中w∈{0，1}∗和M∈{0，1}∗。

Answer 1

L1:让M开始处理w。如果它将读/写头向左移动，您可以立即停止-拒绝，因为我们知道答案。否则，它最终将读取整个有限输入，并进入输入右侧的空格，之后所有磁带单元都为空。现在，继续允许TM运行。如果它将读/写头向左移动，则再次执行halt-reject。否则，我们需要做的就是检测TM首次进入同一状态的时刻两次。为什么会这样呢？如果TM在读取所有输入之后进入某一状态两次，并且已经在输入右侧的空白处，则TM已进入闭合周期，并且将继续在周期中的状态之间转换，同时永远向右移动磁头。根据鸽洞原理，在保证停止、向左移动或重复状态之前，您只需检查与TM状态一样多的转换。当然，如果TM在将读/写头向左移动之前的任何时刻转换为halt-accept或halt-reject，您也会得到您的答案。这意味着这个问题是可以决定的。

L2:让M‘是我们想要解决停顿问题的任何TM。对于M‘中的每个状态Q，我们可以添加一个新的状态Q’，其唯一功能是用从Q到Q‘的转换和从Q到Q’的转换来替换M‘中没有移动读/写头的转换，使得M'’具有M‘的两倍的状态，并且没有保持读/写头静止的转换。现在，我们可以将所有转换更改为halt-accept或halt-reject，以便它们保持磁头不动(没有理由不这样做)；称之为M‘。TM M‘的特性是，它确切地接受M’接受的东西，完全拒绝M‘拒绝的东西，在M’永远循环的地方永远循环，并且包含仅当它在输入上显式停止时才保持读/写头静止的转换。现在，假设我们的问题是可判定的；也就是说，我们可以决定一个任意的TM在处理某些输入w时是否保持磁头静止。然后我们可以决定M‘在处理w时是否保持磁头静止。但是，由于M’的构造方式使得只有当TM停止时磁头才是固定的，这告诉我们M‘在w上暂停(或不停止)。这允许我们决定任意TM M’的暂停问题。这是一个确凿的结论，所以我们的问题是无法决定的。