integer-division - 如何设计图灵机以进行两个数字的除法？

Question

机器以一元形式取2个自然数(a, b)作为输入，输出整数商和整数除法的余数a/b。
磁带上的初始和最终状态是什么？功能图会是什么样子？

提前致谢。

Answer 1

此处使用的设计如下:

从表示 a 的磁带部分划掉 1 的 b 个实例，并在每次执行时增加表示商 q 的磁带的新部分。

如果 b 中的 1 比用于表示 a 的部分中剩余的 1 多，请停止除法；剩余的符号代表余数，无论您当前的商是什么，这就是答案

实现可能会执行以下操作:

将输入作为#11...1011...1#，其中第一个字符串 1 表示一元中的 a，第二个字符串表示一元中的 b，# 是一个空白，磁带头最初从最左边的 1 开始；

立即去在磁带的末尾写一个 Q；在这之后的任何东西都是商

检查是否 b > a;如果是这样，请在终止之前运行一些例程以漂亮的格式重写商和余数。通过在 0 上来回弹跳并暂时标记成对单元格进行检查，然后将它们改回 1s。

否则，将 1 的最左边的 b 个实例更改为 X，在最右边的 1 后面添加一个 1，然后从步骤 3 开始重复。通过在 0 上来回弹跳并临时标记包含 b 的 1 来标记 b 个实例，以便您不要重复计算；然后，将它们改回 1s。

例子:

initial tape: #11111011#
after step 2: #11111011Q#
after step 3: (same)
after step 4: #XX111011Q1#
after step 3: (same)
after step 4: #XXXX1011Q11#
after step 3: #1101# (formatted)