表明在空输入上两次访问起始状态的TMS集是不确定的

Question

我正在尝试证明

$ l_1 = { langle m rangle mid m text {是Turing Machine and Vistits} Q_0 Text {至少两次ON} varepsilon } notin r $。

我不确定是否要减少停止问题。我试图为$（ langle m rangle，w）构建新机器$ m'$，以便$ m'$ visit $ q_0 $ q_0 $两次，如果$ m $ m $ w $停止。这是给我的特定$ q_0 $，但我没有来任何智能构造，这会产生所请求的。也许更容易证明它是$ re $而不是$ core $？显然，它是$ re $，我需要证明$ l_2^{c} $不在$ re $中。

我应该怎么办？

Answer 1

不要使它比现在更复杂。我将不给您完整的解决方案，而是给您部分解决方案，这应该使您可以自己解决细节：

每个TM都会变成一次访问其初始状态一次的TM。为此，引入一个新的状态$ q^'_ 0 $，这将是新的开始状态。然后将$ varepsilon $ - 从$ q^'_ 0 $转移到$ q_0 $。这是“离开”状态$ q'_0 $的唯一方法。

对于这款修改后的计算机，一次接受运行一次访问初始状态，并以接受状态结束。剩下要做的就是进一步修改机器，以便在机器处于接受状态后，它跳回$ q^'_ 0 $。但是，您必须确保第二次访问$ q^'_ 0 $时，您将跳至新的接受状态。但是记录您访问州的频率并不难。

如果您希望另一个状态被访问两次，那么您总是可以在访问此状态的一开始绕道（您记录机器处于“弯路”模式是在特殊磁带上写一张标志）。比您重新布局正常计算，如果应该访问请求的状态，它将访问该状态的副本。最后，当接受时，您跳回请求的状态。从概念上讲，重新标记国家并没有很大不同。