TOC中有哪些不可判定的问题？

对于我们无法构建可以在无限时间内正确回答问题的算法的问题，在计算理论(TOC)中称为不可判定问题。

如果没有图灵机永远停止无限量的时间来回答“是”或“否”，那么问题就是不可判定的。

例子

下面解释了不可判定问题的例子。在这里，CFG 指的是上下文无关语法。

停机问题

停机问题是不可判定问题中最著名的问题。

考虑代码

num=1;
while(num=0)
{
   num=num+1;
}

它永远计数，因为它永远不会等于 0。这是停机问题的一个例子。

注意：每种上下文无关语言都是可判定的。

其他一些无法确定的问题是：

Totality problem - 它决定任意 TM 是否在所有输入上停止。这等价于程序是否可以进入无限循环的问题，对于任何输入。它不同于停机问题，停机问题询问它是否为特定输入进入无限循环。

等价问题- 它决定两个 TM 是否接受相同的语言。这相当于两个程序是否为每个输入计算相同的输出的问题。