证明存在接受下一个语言的TM

Question

我知道如何逼近问题，但我不确定它。 考虑到一个图灵机，我可以检查机器有多少状态，并且不知何故，以某种状态来知道运行是否使用磁带的无休止单元格。 但是，我不确定如何使用状态的数量以及我应该检查的内容。 让我混淆的是，进入无尽环路不一定需要使用胶片的无尽细胞。

$ l_k={ |\，m \，\，\，是\，\，a \，\，tm \，\，\，\，\，\，use \，\，at \，\，大多数\，\，k \，\，磁带\，\，celler \，\，\，\，\，\，\，运行\，\，\，on \，\，\，\ epsilon \} $

证明： $ l ^ *=bigcup \ limits_ {k \，\ in \，\ mathbb {n}} l_k \ in \，\ in \，\，\，re \ setminus r $

Answer 1

语言 $ l ^ * $ 包含所有图灵机 $ m $ ，最终停止或重复配置。对于每台机器 $ M $ ，通过模拟机器，您可以轻松地观察到其中一个可能性发生了。