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

Question

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

L = {M | M is a Turing machine description and there exists an input x of length k such that M halts after at most k steps}

我认为是，但我无法证明。我试图从停机问题中考虑减少。

Answer 1

回顾:停机问题的一个实例询问转动机器 N 是否在输入 y 上停机。已知问题是不可判定的(但半可判定的)。

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

对于停机问题实例 (N, y)，为 L 问题创建一台新机器 M。

在输入 x 上，M 模拟 (N, y) 的 length(x) 步长。

如果模拟在该步数内停止，则 M 停止。否则，M 会故意进入无限循环。

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

如果 (N, y) 最终在 k 步中停止，则 M 将停止所有长度为 k 或更大的输入，因此 M 在 L 中。

否则 (N, y) 不停止，那么 M 对任何输入字符串无论多长都不会停止，因此 M 不在 L 中。

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