解释可判定和不可判定的问题
在我们了解计算理论(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={Moninputw当它的头在最左边的磁带单元上时，它曾经试图向左移动它的头}。
现在，我们的想法是构建一个图灵机S，它以使用R的方式决定ATM。
在输入时，S首先将机器M修改为M´，以便M´仅当M接受其输入时才将其头部从最左侧的单元格向左移动。
为了确保在计算过程中M´不会将头部从最左边的位置向左移动，
第一台机器M´将输入w向右移动一个位置，并在最左侧的磁带单元上放置一个特殊符号。M´的计算从第二个磁带单元上的磁头开始。
在其计算过程中，M´曾尝试将其磁头移动到最左侧的磁带单元，M´通过读取特殊符号发现并将磁头放回第二个单元，并继续执行。如果M进入接受状态，则M´进入一个循环，迫使头部始终向左移动。
在S构建了M´之后，它在输入
如果R接受则S接受，否则如果R拒绝则S拒绝。
因此，ATM是可判定的，这是一个矛盾。