对于我们无法构建可以在无限时间内正确回答问题的算法的问题，在计算理论(TOC)中称为不可判定问题。
如果没有图灵机永远停止无限量的时间来回答“是”或“否”，那么问题就是不可判定的。
例子
下面解释了不可判定问题的例子。在这里，CFG 指的是上下文无关语法。
两个 CFG L 和 M 是否相等 - 由于我们无法确定任何 CFG 的所有字符串，我们可以预测两个 CFG 是否相等。
给定一种上下文无关的语言，没有图灵机 (TM) 会始终停止无限量的时间并给出语言是否含糊不清的答案。
给定两种上下文无关语言，没有图灵机可以永远停止无限量的时间并给出两种上下文无关语言是否相等的答案。
CFG 是否会生成输入字母表 (∑*) 的所有可能字符串是不可判定的。
停机问题
停机问题是不可判定问题中最著名的问题。
考虑代码
num=1;
while(num=0)
{
num=num+1;
}它永远计数，因为它永远不会等于 0。这是停机问题的一个例子。
注意：每种上下文无关语言都是可判定的。
其他一些无法确定的问题是：
Totality problem - 它决定任意 TM 是否在所有输入上停止。这等价于程序是否可以进入无限循环的问题，对于任何输入。它不同于停机问题，停机问题询问它是否为特定输入进入无限循环。
等价问题- 它决定两个 TM 是否接受相同的语言。这相当于两个程序是否为每个输入计算相同的输出的问题。