检查图灵机是否在接受单词之前至少传递k> 2状态

Question

$ l={\ langle m，k \ rangle \ mid \存在w \ l（m）\ text（例如$ m $ 5 在接受$ w $} \}之前，$ k> 2 $ distinct状态。$

我试图考虑减少以证明这种语言既不是重复也不是核心。 如何接近这个问题？有没有提示或直觉？

我通常检查是否可以使用米饭，但这里的问题不是关于语言本身

Answer 1

显然

$ l $ 是可接受的（只是模拟 $ m $ 并跟踪数量模拟期间遇到的明显状态）。我们现在表明它不是可判定的。

如果 $ l $ 是可解除的，您将能够解决暂停问题，如下所示： 给定TM $ t $ 和一个输入 $ x \ in \ sigma ^ * $ ，构建一个tm $ m $ 忽略它的输入，模拟 $ t $ 使用输入 $ x $ ，并且当模拟完成时，接受。 您可以进一步确保，如果 $ m $ 接受，那么它也至少遍历 $ 3 $ 不同的状态通过在开始模拟 $ t $ 之前，通过从初始状态转换到另一个（独特的）状态。

现在检查 $ \ langle m，3 \ rangle \ in l $ 。如果答案是肯定的，那么有一些 $ w \ in \ sigma ^ * $ ，其中 $ m（w） $ 接受，显示 $ t（x）$ 停止。 如果答案是否定的，那么<跨越类=“math-container”> $ m $ 永远不会停止，显示 $ t（x）$ 停止。