如何设计用于将两个数相除的图灵机？

Question

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

提前感谢。

Answer 1

这里使用的设计如下：

1. 从代表a的磁带部分中减去1的b个实例，并在每次执行时将代表商q的磁带的新部分递增。

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

一个实现可能会执行以下操作：

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

2. 立即在磁带的末尾写一个Q；商之后的所有内容

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

4. 否则，将b的最左边的实例1更改为X，在最右边的1之后添加1，然后从步骤3开始重复。通过在0上来回弹跳并暂时标记1s来标记b实例。由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)