AmodB函数图灵机

Question

我想知道如何计算函数 A mod B，其中 A > B 和 A、B 是一元数，具有确定性图灵单带机器。

谢谢

Answer 1

给定像 B111...10111...1BBB... 这样的输入，其中第一个 1 字符串是 a 的一元编码（即 1^a），第二个 1 字符串是一元编码b 的编码（即 1^b），我们可以设计一个单带确定性图灵机来计算 a mod b（通过在离开 a mod b 的一元表示后输入 halt-accept在磁带上）。

首先注意 a mod b < a，因此我们可以通过从 a 的一元表示中删除一些 1 来恢复 a mod b 的一元表示，并从中删除所有 1 b 的一元表示。观察 a mod b = (a - b) mod b，至少当 a >= b 时；当 a < b 时，则 a mod b = a。这一观察表明，我们可以从 a 的一元表示中删除 b 1，直到剩余的 1 少于 b，此时我们从 b 的表示中删除 1 并停止接受。

伪代码：

move right until you find a blank.
move one step to the left.
you are now looking at the last 1 in b's representation.
mark this as Y and move left until you find 0.
move left until you find a 1 or blank.
you are now looking at the last 1 in a's representation, or blank.
if 1, mark this as X and move right until you find Y.
if blank, a < b; change all Xs to 1s and all 0s, 1s and YBs to blanks. halt-accept.
move one step to the left.
you are now looking at the last 1 in b's representation, or 0.
if 1, continue as above.
if 0, b < a; change all Xs to 0s, all Ys to 1s, and restart from the beginning

示例：10 mod 3

B11111111110111BBB...
^

B11111111110111BBB...
               ^        move right until you find a blank

B11111111110111BBB...
              ^         move one step to the left. looking at last 1 in b

B1111111111011YBBB...
           ^            mark as Y and move left to 0

B1111111111011YBBB...
          ^             move one step to the left. looking at last 1 in a.

B111111111X011YBBB...
              ^         mark as X and move right to Y

B111111111X011YBBB...
             ^          move one step to the left. looking at last 1 in b.

B111111111X01YYBBB...
           ^            mark as Y and move left to 0

B111111111X01YYBBB...
         ^              move left to 1

B11111111XX01YYBBB...
             ^          mark as X and move right to Y

B11111111XX01YYBBB...
            ^           move one step to the left. looking at last 1 in b

B11111111XX0YYYBBB...
           ^            mark as Y and move left to 0

B11111111XX0YYYBBB...
        ^               move left to 1

B1111111XXX0YYYBBB...   mark as X and move right to Y
            ^

B1111111XXX0YYYBBB...   move one step left. looking at 0; b < a
           ^

B11111110000111BBB...
^                       change Xs to 0s and Ys to 1s; start over.

(above process repeats two more times)

B10000000000111BBB...
^                       erased 3x 1s from a 3x times

B10000000000111BBB...
               ^        move right to blank

B10000000000111BBB...
              ^         move one step left. looking at last 1 in b

B1000000000011YBBB...
           ^            mark as Y and move left to 0.

B1000000000011YBBB...
 ^                      move left to 1

BX000000000011YBBB...
              ^         mark as X and move right to Y

BX000000000011YBBB...
             ^          move one step left. looking at last 1 in b.

BX00000000001YYBBB...
           ^            mark as Y and move left to 0

BX00000000001YYBBB...
^                       move left to blank. a < b.

B1BBBBBBBBBBBBBBBB...
^                       change Xs to 1s and 0s, 1s, Ys to blank. halt-accept

AmodB函数图灵机

A mod B function Turing machine

turing-machines