图灵机：取两个数字的模？

Question

设计一个图灵机，输入两个非负数并对它们进行模运算，例如 mod(3,7)=3 和 mod(7,3)=1。显然，指定有关 TM 输入和输出的任何假设和格式。

Answer 1

输入是两个由分隔符分隔的一元正整数 X 和 Y。输出是一元中的单个数字 Z。TM 是单面单带确定性。

首先，向右移动找到分隔符。然后，在 X 的结尾和 Y 的开头之间来回弹跳，标记符号对。如果在用完 Y 之前用完 X，则 X < Y 且 X mod Y = X；擦除分隔符及其后的所有内容，然后将所有磁带符号更改为您的一元数字并停止接受。如果在 X 之前用完 Y，则将 X 中的标记符号更改为擦除/分隔符，将 Y 的标记符号恢复为一元数字，然后重复 (X >= Y, so X mod Y = (X - Y) mod Y ）。

以下是处理 2 mod 3 的方式：

#110111#
#1a0b11#
#aa0bb1#
#aa#####
#11#####

以下是 3 mod 2 的处理方式：

#111011#
#11a0b1#
#1aa0bb#
#100011#
#a000b1#
#a######
#1######