$ l（m）= l $其中$ m $是$ tm $，仅移至右侧，所以$ l $是常规

Question

假设$ l（m）= l $其中$ m $是$ tm $，仅移至右侧。

我需要证明$ l $是常规的。

我很喜欢一些帮助，我试图考虑任何证明这一点的方法，但我没有得出任何明智的结论。唯一的右侧移动和规律性是什么？

Answer 1

提示 - 您需要证明您的TM具有与有限状态自动机相同的功率（正如评论员Dave Clarke所说），也就是说，鉴于这样的TM，构建了接受相同语言的FSA。

但是，由于TM没有记忆，但是磁带没有记忆，请问自己，仅适合TM的TM可以用胶带做些什么。实际构建所需的FSA部分应该相对简单。只需浏览它们 - 状态，输入字母和最关键的移动函数（通常是$ delta $），并根据您启动的TM部分定义它们。然后，您必须证明两者在每个人的“接受”定义方面接受相同的语言，请确保提及TM中的潜在循环行为。

顺便说一句，这种问题适合一个令人信服的“挥手”证明，实际上是一种在研究论文中可以接受的类型。但是，您的课程可能会期望使用$ delta $以及构成TM和FSA的元组的其他组件。

Answer 2

有限自动机和图灵机之间的唯一区别是胶带。磁带提供内存能力。如果您只能在一侧走，那么您根本无法阅读所写的内容。

为了正式证明这一点，您是从机器$ m $构建自动机。假设$ a $是$ m $中的自动机。然后，您的自动机$ a'$将与带有单元内存的$ a $相同，因为您仍然可以阅读$ m $中的单元格。 （$ a'$ = $ m $ $×$的状态数量的状态数量）。

请注意，如果您只能读取距右边距离单元格最距离的单元格，那么这仍然是正确的，因为您仍然具有有界的内存。另外，磁带的数量以及您是从磁带中读取的，还是像DFA这样的“标准输入”都无关紧要。