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

Question

下面的语言L是不可判定的吗？

L = {米| 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步中停止，则M将对长度为k或更大的所有输入停止，因此M在L中。
• 否则 ( N , y ) 不会停止，那么无论输入字符串有多长，M都不会停止，因此M不在L中。

最后，停止问题是不可判定的，因此L是不可判定的。