#navi2(shaのPukiWiki実験ページ,top,prev,next,end,toc) *チューリングマシンエミュレータ [#l5632c95] #areaedit ロジャー・ペンローズ著の「[[皇帝の新しい心>[[ISBN:4622040964]]]]」のチューリングマシンを実装。 -引数の仕様 #turing(prog) <program> #turing(<max step count>,[skip|UN|XN]) <全メモリの初期値> -<program>の仕様 Start→<次のlabel> <label>[<現在のメモリ値>]→[<変更後のメモリ値>] <メモリの移動方向> <次のlabel> <label>[<現在のメモリ値>]→[<変更後のメモリ値>] Stop -<引数の意味> <max step count>: 実行する回数 skip: 読み取りメモリの状態が変わらない場合は表示しない。 UN: <全メモリの初期値>に記載の数値の解釈として「1の数」を使用。 XN: <全メモリの初期値>に記載の数値の解釈として「拡張2進数」を使用。 <全メモリの初期値>: 実行に先だって用意しておくメモリ内容。詳細は下記。 <次のlabel>: 次に実行する命令のラベル（マシンの内部状態） <現在のメモリ値>: 現在のメモリ内の位置の指し示す値 <変更後のメモリ値>: メモリ内の今の位置の値をこの値に変更 <メモリ移動方向>: L（メモリ内で左へ１つ移動）| R（メモリ内で右へ１つ移動） -プログラム行の例 120[0]→[1] L 121 ラベルが120で、現在地のメモリが[0]の時、メモリを[1]に変更して、左へ一つメモリ位置を移動し、ラベル121へ制御を移すする。 -<全メモリの初期値>の例 '1'と'o'の組み合わせ oooooooo1111oo11111ooooooooo または、'<数字>,'の並び（UN,XNが引数に指定されている場合） 4,5, -目次 #contents ---- #areaedit(end) #addline(領域編集,below,ltext:―――――,btn:テスト領域を増やす,rtext:―――――) #areaedit #areaedit(end) #areaedit #areaedit(end) #areaedit * [XN+1] ２進で１足す [#q8317a08] XNは下記のように符号化 0←0 10←1 110←数字の終わり よって、9(10進数)は、1001(2進数)、100010110(XN)と符号化できる。 ~９＋１（1001+1） #turing(prog) 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(100,skip,XN) 60, // 9, // ooooo10001011oooooooo #areaedit(end) #areaedit *[XN*2] ２進表記で２倍 [#d0e9d047] ~１１×２（1011） #turing(prog) 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(50,XN) 11, // ooooo100101011oooooo #areaedit(end) #areaedit * [UN+1]１を加える。３＋１ [#gce0fd33] 数値の表現をどう扱うかは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(prog) Start→10 10[0]→[0] R 10 10[1]→[1] R 20 20[0]→[1] Stop 20[1]→[1] R 20 #turing(70,UN) 60, // 5, // ooo111oooooo #areaedit(end) #areaedit * [EUC]互除法 [#kce00b40] 最大公約数を求める。６と９で３、１５と１０で５ #turing(prog) 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(1000,skip,UN) 15,10, // ooooooo111111ooooo111111111oooooo #areaedit(end)