#freeze
#navi2(shaのPukiWiki実験ページ,top,prev,next,end,toc)

*チューリングマシンエミュレータ [#l5632c95]
#areaedit
ロジャー・ペンローズ著の「[[皇帝の新しい心>[[ISBN:4622040964]]]]」のチューリングマシンを実装。
-引数の仕様
 #turing(prog)
 <program>
 #turing(<max step count>,[skip])
 #turing(<max step count>,[skip|UN|XN])
 <全メモリの初期値>
-<program>の仕様
 Start→<次のlabel>
 <label>[<現在のメモリ値>]→[<変更後のメモリ値>] <メモリの移動方向> <次のlabel>
 <label>[<現在のメモリ値>]→[<変更後のメモリ値>] Stop
-<引数の意味>
 <max step count>: 実行する回数
 skip: 読み取りメモリの状態が変わらない場合は表示しない。
 <全メモリの初期値>: 実行に先だって用意しておくメモリ内容
 UN: <全メモリの初期値>に記載の数値の解釈として「1の数」を使用。
 XN: <全メモリの初期値>に記載の数値の解釈として「拡張2進数」を使用。
 <全メモリの初期値>: 実行に先だって用意しておくメモリ内容。詳細は下記。
 <次のlabel>: 次に実行する命令のラベル(マシンの内部状態)
 <現在のメモリ値>: 現在のメモリ内の位置の指し示す値
 <変更後のメモリ値>: メモリ内の今の位置の値をこの値に変更
 <メモリ移動方向>: L(メモリ内で左へ1つ移動)| R(メモリ内で右へ1つ移動)

-プログラム行の例
 120[0]→[1] L 121
ラベルが120で、現在地のメモリが[0]の時、メモリを[1]に変更して、左へ一つメモリ位置を移動し、ラベル121へ制御を移すする。
-<全メモリの初期値>の例
'1'と'o'の組み合わせ
 oooooooo1111oo11111ooooooooo
または、'<数字>,'の並び(UN,XNが引数に指定されている場合)
 4,5,
-目次
#contents
----
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)

#addline(領域編集,below,ltext:―――――,btn:テスト領域を増やす,rtext:―――――)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
#areaedit(end)
#areaedit
* [XN+1] 2進で1足す [#q8317a08]
XNは下記のように符号化
  0←0
  10←1
  110←数字の終わり
よって、9(10進数)は、1001(2進数)、100010110(XN)と符号化できる。
~9+1(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)
 ooooo10001011oooooooo
#turing(100,skip,XN)
 60,
// 9,
// ooooo10001011oooooooo
#areaedit(end)
#areaedit
*[XN*2] 2進表記で2倍 [#d0e9d047]
~11×2(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)
 ooooo100101011oooooo
#turing(50,XN)
 11,
// ooooo100101011oooooo
#areaedit(end)
#areaedit
* [UN+1]1を加える。3+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(20)
 ooo111oooooo
#turing(70,UN)
 60,
// 5,
// ooo111oooooo
#areaedit(end)

#areaedit
* [EUC]互除法 [#kce00b40]
最大公約数を求める。6と9で3
最大公約数を求める。6と9で3、15と10で5

#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)
 ooooooo111111ooooo111111111oooooo
#turing(1000,skip,UN)
 15,10,
// ooooooo111111ooooo111111111oooooo
#areaedit(end)


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS