解释可判定和不可判定的问题
在我们了解计算理论 (TOC) 中的可判定和不可判定问题之前，我们必须了解可判定和不可判定语言。因此，让我们首先看看可判定语言是什么意思。
可判定语言
如果存在一个决定器 M 使得L( M)= L，则语言 L 被称为可判定的。
给定决策者 M，您可以了解字符串 w ∈ L(M)。
在 w 上运行 M。
尽管可能需要很长时间，但 M 会接受或拒绝 w。
集合 R 是所有可判定语言的集合。
如果 L 是可判定的，则 L ∈ R。
不可判定的语言
如果 P 的所有 yes 实例的语言 L 不可判定，则判定问题 P 是不可判定的。
不可判定语言可能是部分可判定但不可判定的。假设，如果一种语言甚至不能部分判定，那么对于相应的语言就不存在图灵机。
问题
找出下面给出的问题是可判定的还是不可判定的。
“让给定的输入是一些图灵机 M 和一些字符串 w。问题是确定在输入字符串 w 上执行的机器 M 是否曾经连续三个增量规则将其读数头向左移动。”
解决方案
定义 M' 是一个图灵机，它以一对 (M,w) 作为输入，其中 M 是被 M' 识别的图灵机，w 是 M 的输入。
每当模拟机器 M 的头部在处理输入 w 时向左移动，M' 停止并接受 (M,w)
对于 M' (M,w) 的特定输入，图灵机 P 的构造是 -
P 在 (M,w) 上执行 M'
如果 M' 接受 (M,w)，则 P 停止并接受任何输入
我们试图将通用图灵机 U 简化为 P，因为我们知道它L(U)是不可判定的，并且我们得出结论它L(P)是不可判定的。因此，M' 是不可判定的。
证明是自相矛盾的。
让我们假设这个问题是可判定的，然后我们必须证明改变图灵机(ATM)也是可判定的 -
ATM = { M 是一个 TM 并且 M 接受 w}。
设 R 是决定最左边问题的图灵机。
也就是说，R决定语言
leftmost = { M on input w 当它的头在最左边的磁带单元上时，它曾经试图向左移动它的头}。
现在，我们的想法是构建一个图灵机 S，它以使用 R 的方式决定 ATM。
在输入时，S 首先将机器 M 修改为 M´，以便 M´ 仅当 M 接受其输入时才将其头部从最左侧的单元格向左移动。
为了确保在计算过程中 M´ 不会将头部从最左边的位置向左移动，
第一台机器 M´ 将输入 w 向右移动一个位置，并在最左侧的磁带单元上放置一个特殊符号。M´ 的计算从第二个磁带单元上的磁头开始。
在其计算过程中，M´ 曾尝试将其磁头移动到最左侧的磁带单元，M´ 通过读取特殊符号发现并将磁头放回第二个单元，并继续执行。如果 M 进入接受状态，则 M´ 进入一个循环，迫使头部始终向左移动。
在 S 构建了 M´ 之后，它在输入 < M´ 上运行决策器 R；w>.
如果 R 接受则 S 接受，否则如果 R 拒绝则 S 拒绝。
因此，ATM 是可判定的，这是一个矛盾。
以上是 解释可判定和不可判定的问题 的全部内容， 来源链接： utcz.com/z/338764.html
