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

Question

设计一个图灵机，输入两个非负数并对它们执行mod运算，例如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中的标记符号改为erased/separator，将Y的标记符号恢复为一元数，重复(X>=Y，所以Xmod Y = (X - Y) mod Y).

处理 2 mod 3 的方式如下：

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

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

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

Answer 2

下面给出一些基本信息

![在此处输入图片描述

完整图如下。这里 # 为空或 null.Idea 与上面给出的相同。以下是您的 2 mod 3 的处理方式：

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

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

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

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

Turing Machine: take a mod of two numbers?

automata

turing-machines