A mod B函数图灵机

Question

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

由于

Answer 1

鉴于像B111 ... 10111 ... ... 1BBB，输入其中的1的第一字符串是（即，1^A）的一元编码和所述第二串1s是b的一元编码（即1^b），我们可以设计一个单带确定性图灵机来计算一个mod b（通过在留下磁带上留下的一个mod b的一元表示后进入暂停接受） 。

首先注意一个mod b < a，所以我们可以通过从a的一元表示中删除一些1，并从b的一元表示中删除所有的1来恢复mod b的一元表示。注意到mod b =（a - b）mod b，至少当a> = b;当一个< b，那么一个mod b = a。这个观察结果表明，我们可以从a的一元表示中删除b 1，直到剩余的b 1少于b 1，此时我们从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