证明这种语言是不可判定的

Question

在下面的语言大号不可判定？

L = { M | M是图灵机描述,并且存在长度为k的输入x,使得M在最多k步之后停止}

我想是的但是我无法证明这一点.我试着想到减少停止问题.

Answer 1

检查:暂停问题的一个实例询问车床N是否在输入y上停止.众所周知,这个问题是不可判定的(但是可以说是半封闭的).

你的语言L确实是不可判定的.这可以通过将停止问题减少到L来显示:

1. 对于暂停问题实例(N,y),为L问题创建一个新机器M.
2. 在输入x上,M模拟(N,y)长度(x)步长.
3. 如果模拟在该步数内停止,则M停止.否则,M故意进入无限循环.

这种减少是有效的,因为:

• 如果(N,y)最终以k步骤停止,那么对于长度为k或更大的所有输入,M将停止,因此M在L中.
• 否则(N,y)不会停止,那么无论多长时间M都不会停止任何输入字符串,因此M不在L中.

最后,暂停问题是不可判定的,因此L是不可判定的.