如何设计两个数字除法的图灵机?

Question

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

提前谢谢。

Answer 1

此处使用的设计如下：

从表示 A 的磁带部分

1. 划掉 B 实例 1，并在每次执行此操作时递增表示商 q 的磁带的新部分。

2. 如果你在 B 中的 1 比过去代表 A 的部分的剩余部分多，请停止除法;剩下的符号代表余数，无论你当前的商是什么，这就是答案

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

将输入为 #11...1011...1#，其中第一个字符串 1 表示一元

1. 中的 a，第二个字符串表示一元中的 b，# 为空白，磁带头最初从最左边的 1 开始;

2. 立即在磁带末尾写一个Q;在此之后的任何内容都是商。

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

4. 否则，将 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)