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