turing-machines - 设计图灵机

Question

我需要帮助设计一台可以计算以下内容的图灵机f(x) = x mod 3。我只需要帮助开始，因为我不熟悉如何解决这个问题

Answer 1

评论摘录：

输入和输入是一元字符串1。空间是0。输出应该重写输入。

输入是 {x, 3}，每个参数或 {x} 之间有一个空格。

输出为 {x mod 3}。

算法：

• 转到输入的末尾。
• 删除第二个参数。
• 当参数中至少有三个符号时，删除它们。

状态机：

• 开始：如果输入为0，则向右移动并转到“删除右侧”，否则向右移动。
• 向右删除：如果输入为0，则向左移动并转到“查找arg”。否则写 0 并向右移动。
• 查找 arg：如果输入为 0，则向左移动。如果输入是“磁带开始”，则结束。否则向左移动并进入状态“found 1”。
• 找到 1：如果输入是“磁带开始”，则结束。否则向左移动并进入“找到 2”状态
• 找到 2：如果输入是“磁带开头”，则结束。否则进入“删除权”状态。