ロジャー・ペンローズ著の「皇帝の新しい心」のチューリングマシンを実装。
#turing(prog) <program> #turing(<max step count>,[skip]) <全メモリの初期値>
Start→<次のlabel> <label>[<現在のメモリ値>]→[<変更後のメモリ値>] <メモリの移動方向> <次のlabel> <label>[<現在のメモリ値>]→[<変更後のメモリ値>] Stop
<max step count>: 実行する回数 skip: 読み取りメモリの状態が変わらない場合は表示しない。 <全メモリの初期値>: 実行に先だって用意しておくメモリ内容 <次のlabel>: 次に実行する命令のラベル(マシンの内部状態) <現在のメモリ値>: 現在のメモリ内の位置の指し示す値 <変更後のメモリ値>: メモリ内の今の位置の値をこの値に変更 <メモリ移動方向>: L(メモリ内で左へ1つ移動)| R(メモリ内で右へ1つ移動)
XNは下記のように符号化
0←0 10←1 110←数字の終わり
よって、9(10進数)は、1001(2進数)、100010110(XN)と符号化できる。
9+1(1001+1)
Turing's program
Start→100 100[0]→[0] R 100 100[1]→[1] R 101 101[0]→[0] R 100 101[1]→[1] R 102 102[0]→[0] L 103 102[1]→[1] R 102 103[0]→[1] Stop 103[1]→[0] L 104 104[0]→[1] L 105 104[1]→[1] L 104 105[0]→[0] R 106 105[1]→[1] R 102 106[1]→[1] R 107 107[0]→[1] R 103 107[1]→[0] R 107
Turing's Execution
ooooo10001011oooooooo
11×2(1011)
Turing's program
Start→10 10[0]→[0] R 10 10[1]→[0] R 11 11[0]→[1] R 10 11[1]→[0] R 12 12[0]→[1] R 13 13[0]→[1] Stop
Turing's Execution
ooooo100101011oooooo
数値の表現をどう扱うかはprogram次第だが、下記のプログラムでは1の数で数値を示す。
7(10進数)は、11111110(UN)と符号化している。
#turing(prog) Start→10 10[0]→[0] R 10 10[1]→[1] R 20 20[0]→[1] Stop 20[1]→[1] R 20 #turing(30) ooo111oooooo ←初期値
Turing's program
Start→10 10[0]→[0] R 10 10[1]→[1] R 20 20[0]→[1] Stop 20[1]→[1] R 20
Turing's Execution
ooo111oooooo
最大公約数を求める。6と9で3
Turing's program
Start→100 100[0]→[0] R 100 100[1]→[1] L 101 101[0]→[1] R 102 101[1]→[1] L 101 102[0]→[0] R 110 102[1]→[0] R 103 103[0]→[0] R 104 103[1]→[1] R 103 104[0]→[0] R 104 104[1]→[0] R 105 105[0]→[0] L 107 105[1]→[1] L 106 106[0]→[0] L 106 106[1]→[1] L 101 107[0]→[0] L 107 107[1]→[1] L 108 108[0]→[0] L 109 108[1]→[1] L 108 109[0]→[0] R 102 109[1]→[1] L 101 110[0]→[0] Stop 110[1]→[1] R 110
Turing's Execution
ooooooo111111ooooo111111111oooooo