圖靈機：取兩個數字的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中的標記符號更改爲擦除/分隔符，將Y的標記符號恢復爲一元數字，並重復（X> = Y，因此X mod Y =（X-Y）mod Y ）。

這是你的2模3如何得到處理：

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

這裏的3 MOD 2如何得到處理：

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