java - 如何模拟图灵机？

Question

我不太了解图灵机的整个想法。

我目前的任务是制造一台繁忙的海狸图灵机。但我没有真正得到的是它模拟输入。那么我模拟什么样的输入呢？例如，它问我 3 州忙碌的海狸机器在磁带上写了多少个 1？我确定我需要写一个图灵机，但是一旦我有了它，我该怎么办呢？

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

Answer 1

您的第一步将是更好地理解“图灵机的整个想法”。您可以尝试阅读它：

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

Answer 2

对于忙碌的海狸场景，通常假设没有特殊的输入，即图灵机的磁带最初是空的。当然，在运行期间，忙碌的海狸可能会写入磁带，然后再读取它所写入的内容。

所以你必须模拟磁带。由于它应该在两端都是无限的，我建议通过子类ArrayList化和覆盖get()and方法来实现它，将正索引映射到偶数元素，将负索引映射到奇数元素（并且还可以通过在存在时set()重复调用来自动增加大小add(null)是对当前列表大小之外的索引的访问）。