チューリングマシン：2つの数値のモッズを取る？

Question

mod（3,7）= 3とmod（7,3）= 1のように、2つの非負の数値を入力してmod演算を実行するチューリングマシンを設計します。明らかに、TMの入力と出力に関する仮定と形式を指定します。

Answer 1

入力は、セパレータ記号で区切られた単項の2つの正の整数XとYです。出力は単項では単一のZです。 TMは片面シングルテープであることが決定的である。

まず、右に移動してセパレータを見つけます。次に、Xの終わりとYの始まりとの間を行き来して、記号の対をマーキングする。あなたがYを使い果たす前にXを使い果たした場合、X < YとX mod Y = X;セパレータとその後ろのすべてを消去してから、すべてのテープ記号を単項桁に変更し、halt-acceptします。あなたがXの前にYを使い果たした場合、Xのマークされた記号を消去/区切りに変更し、Yのマークされた記号を単項の数字に復元して、XのY =（X - Y）mod Y ）。

はここにあなたの2のmod 3が処理されます方法は次のとおりです。

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

はここ3 MOD 2が処理されます方法は次のとおりです。

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