如何模拟图灵机？

Question

我不太明白图灵机的整个想法。

我目前的任务是制作一台忙碌的海狸图灵机。但我真正不明白的是它模拟输入。那么我要模拟什么样的输入呢？例如，它询问我 3 状态繁忙的海狸机在磁带上写入了多少个 1？我确定我需要编写一个图灵机，但是一旦我有了它，我该怎么用它呢？

我应该用什么字符串来模拟它？

Answer 1

有关的忙海狸场景时，通常认为没有特殊的输入，即图灵机的磁带最初是空的。当然，它的运行过程中，忙碌的海狸可以写入磁带，后来读它写。

所以，你必须模拟磁带。因为它应该是在两端无限的，我建议通过继承ArrayList并覆盖get()和set()方法映射积极的指数，以偶数元素和负指数，奇数元素（也被反复自动增加的大小来实现它主叫add(null)当在列表中的当前大小之外的索引的访问）。

Answer 2

您的第一步将是更好地理解“图灵机的整体概念”。你可以尝试阅读它：

• 维基百科 这里（简单） 和 这里
• 另一种解释