一个与无用状态的图灵机有关的问题

Question

好的，所以这是我的计算理论类别中过去测试的问题：

TM中无用的状态是从未在任何输入字符串上输入的状态。令$ mathrm {useless} _ { mathrm { mathrm {tm}} = { langle m，q rangle mid q text {是} m }的无用状态。无用} _ { mathrm {tm}} $是不确定的。

我想我有答案，但是我不确定这是否正确。将其包含在答案部分。

Answer 1

这显然可以从停止问题中降低。如果机器$ m $不停止输入$ x $，则任何最终状态都是“无用的”。给定停止问题的输入$ m，x $，当且仅当$ m $ tharts in $ x $停止时，就很容易构造在每个输入上停止的$ m_x $（因此其最终状态并不毫无用处）。这样，如果您可以决定$ mathrm {useless} _ { mathrm {tm}} $，则可以决定停止问题，这产生了矛盾。

Answer 2

出于此证明的目的，我们将假设$ mathrm {useless} _ { mathrm {tm}} $可以决定显示矛盾。

创建执行以下操作的TM $ R $：

• 将TM $ M $转换为带有放松堆栈的Pushdown Automata $ P $（即没有LIFO要求）。这相当于有向图，详细介绍了$ M $的状态之间的过渡。
• 标记$ p $的开始状态。
• 从开始，状态开始沿每个出站边缘进行广度优先搜索，标记每个未标记的节点。
• 搜索终止时，如果有任何未标记的节点匹配$ q $， 接受;否则 拒绝.

然后创建TM $ S $ =“输入$$

1. 如上图所示，创建TM $ R $。
2. 在$ r $上运行$ q $。
3. 如果$ r $退货接受， 接受;如果$ r $拒绝， 拒绝"

因此，如果$ r $是$ mathrm {useless} _ { mathrm {tm}} $的决定者，则$ s $是$ a _ { mathrm {tm}} $的决定剂（接受问题）。由于$ a _ { mathrm {tm}} $被证明是不可决定的（请参阅Michael Sipser 计算理论 第174页的定理4.11），我们达到了矛盾。因此，原始假设是不正确的，$ mathrm {useless} _ { mathrm {tm}} $是不可证实的。