是否递归设置
Recursive set or not
我正在尝试解决大学的问题，但我不知道如何解决。有人能帮我说说我怎么能证明下面提到的两种语言是可判定的还是不可判定的
L1:= M, w |在输入 w 时，图灵机 M 永远不会将 read/write 头向左移动，其中 w ∈ {0, 1} ∗ 并且 M ∈ {0, 1} ∗.
L2:= M, w |在输入 w 上，图灵机 M 在每一步移动 read/write 头，其中 w ∈ {0, 1} ∗ 并且 M ∈ {0, 1} ∗.
L1：让M开始处理w。如果它向左移动 read/write 头，您可以立即停止拒绝，因为我们知道答案。否则，它最终会读取整个有限输入并进入输入右侧的空白区域，之后所有磁带单元都为空白。现在，继续允许 TM 运行。如果它向左移动 read/write 头，再次停止拒绝。否则，我们需要做的就是检测TM第一次进入同一个状态两次的时刻。这是为什么？如果 TM 在读取所有输入后进入某个状态两次并且已经在输入右侧的空白处，则 TM 已进入闭合循环并将继续在循环中的状态之间转换，同时将磁带头向右移动永远。根据鸽巢原则，您只需要检查与 TM 状态一样多的转换，就可以保证停止、向左移动或重复一个状态。当然，如果 TM 在 read/write 头向左移动之前的任何时候过渡到停止接受或停止拒绝，你也有你的答案。这意味着这个问题是可判定的。
L2：让 M' 是我们想要解决停机问题的任何 TM。对于 M' 中的每个状态 Q，我们可以添加一个新的状态 Q'，其唯一功能是替换 M' 中没有移动 read/write 头的转换，转换从 Q 到 Q' 然后再返回，因此 M '' 的状态是 M' 的两倍，并且没有使 read/write 头部保持静止的转换。现在，我们可以将所有转换更改为停止接受或停止拒绝，以便它们保持磁带磁头静止（没有理由不这样做）；称这个为 M'''。 TM M''' 具有 属性 它完全接受 M' 接受的东西，完全拒绝 M' 拒绝的东西，在 M' 永远循环的地方永远循环，并包含使 read/write 头部保持静止的转换仅当它明确停止输入时。现在，假设我们的问题是可判定的；也就是说，我们可以决定任意 TM 在处理某些输入 w 时是否曾使磁头保持静止。然后我们可以决定 M''' 在处理 w 时是否让磁头保持静止。但是，由于 M''' 的构造方式使得磁头仅在 TM 停止时才会静止，这告诉我们 M''' 在 w 上停止（或不停止）。这使我们能够决定任意 TM M' 的停机问题。这是一个荒谬的结论，所以我们的问题是不可判定的。
我正在尝试解决大学的问题，但我不知道如何解决。有人能帮我说说我怎么能证明下面提到的两种语言是可判定的还是不可判定的
L1:= M, w |在输入 w 时，图灵机 M 永远不会将 read/write 头向左移动，其中 w ∈ {0, 1} ∗ 并且 M ∈ {0, 1} ∗.
L2:= M, w |在输入 w 上，图灵机 M 在每一步移动 read/write 头，其中 w ∈ {0, 1} ∗ 并且 M ∈ {0, 1} ∗.
L1：让M开始处理w。如果它向左移动 read/write 头，您可以立即停止拒绝，因为我们知道答案。否则，它最终会读取整个有限输入并进入输入右侧的空白区域，之后所有磁带单元都为空白。现在，继续允许 TM 运行。如果它向左移动 read/write 头，再次停止拒绝。否则，我们需要做的就是检测TM第一次进入同一个状态两次的时刻。这是为什么？如果 TM 在读取所有输入后进入某个状态两次并且已经在输入右侧的空白处，则 TM 已进入闭合循环并将继续在循环中的状态之间转换，同时将磁带头向右移动永远。根据鸽巢原则，您只需要检查与 TM 状态一样多的转换，就可以保证停止、向左移动或重复一个状态。当然，如果 TM 在 read/write 头向左移动之前的任何时候过渡到停止接受或停止拒绝，你也有你的答案。这意味着这个问题是可判定的。
L2：让 M' 是我们想要解决停机问题的任何 TM。对于 M' 中的每个状态 Q，我们可以添加一个新的状态 Q'，其唯一功能是替换 M' 中没有移动 read/write 头的转换，转换从 Q 到 Q' 然后再返回，因此 M '' 的状态是 M' 的两倍，并且没有使 read/write 头部保持静止的转换。现在，我们可以将所有转换更改为停止接受或停止拒绝，以便它们保持磁带磁头静止（没有理由不这样做）；称这个为 M'''。 TM M''' 具有 属性 它完全接受 M' 接受的东西，完全拒绝 M' 拒绝的东西，在 M' 永远循环的地方永远循环，并包含使 read/write 头部保持静止的转换仅当它明确停止输入时。现在，假设我们的问题是可判定的；也就是说，我们可以决定任意 TM 在处理某些输入 w 时是否曾使磁头保持静止。然后我们可以决定 M''' 在处理 w 时是否让磁头保持静止。但是，由于 M''' 的构造方式使得磁头仅在 TM 停止时才会静止，这告诉我们 M''' 在 w 上停止（或不停止）。这使我们能够决定任意 TM M' 的停机问题。这是一个荒谬的结论，所以我们的问题是不可判定的。