今年の3月頃にこのブログに投稿した, 電卓HHCのプログラミングの話題の続きである. この電卓のシミュレータには, スタックが2個あり, その間でデータが受け渡せる. このスタックを, 両方へ延びるテープ, 命令UとNをヘッドの右, 左への移動と思うと, 2スタックモデルはTuring Machineに非常によく似てくる.
そこで今回は, Turing Machineをシミュレートしてみた.
Turingの
1936年の有名な論文の始めの方に, テープに0010110111011110...を書く例がある.
つまり, 0の列の間に1を0個, 1個, 2個, 3個, ...と挟むのである. この論文のテープは, 計算結果を書くますと, 作業用の記号を書くますが, 交互に並んでいる. 従って, 上の出力も,テープ全体で見ると, bを空白のますとして, 0b0b1b0b1b1b0b1b1b1b0b1b1b1b1b0...と出来上がる.
Turingのプログラムは以下のようである. (状態bにPe, つまりeを書くとあるが, Turingの論文では, eを上下反対にした形である.)
state symbol operations next state
b Pe,R,Pe,R,P0,R,R,P0,L,L o
o 1 R,Px,L,L,L o
0 q
q 0or1 R,R q
none P1,L p
p x E,R q
e R f
none L,L p
f 0or1 R,R f
none P0,L,L o
開始の状態はbで, 「eを書き右へ行きeを書き右へ行き0を書き右へ行き右へ行き0を書き左へ行き左へ行き」だから, テープは「ee0 0」となり, ヘッドは左の0のところにあって, 新しい状態はo.
状態oは, 結果のますで, 左へ1が続く限り, その右に作業用のxを書く. 0であったら, 0の場所にいるままで, 状態qへ. 従って, 最初はすぐqになる.
状態qでは, 結果のますに0が1がある限り右へ行き, 空白を見つけたら1を書き, 左へ進み(つまり作業ますに移り), pになる.
pでは, 作業用のますを左に見て生き, xに出会えば, それを消してqになるから, 右の空白に1を書きpに戻る. つまりxの数だけ, 右に1を書く. その前に, oからqに移ってきた時にも1を書いたから, xの数より1個多く1を書く. xが見つからず, 左端のeが見つかれば, 右に行き, 結果のますに移ってfになる.
状態fでは結果のますを右に見ていき, 空白を見つけたら0を書き, 左へ2歩行き, 1の真下にいて, oに戻る.
oは前に述べた通り, 1が続くとxを併記していき, 次回1を書き続ける時の準備をする.
とりあえずSchemによるシミュレーションはを下に示す. テープ長は50で, それを越えて読み書きしようとすれば, プログラムを修了する. 記号e, x, 空白を, 2, 3, 4で表現する.
(define e 2) (define x 3) (define n 4)
(define tapelength 50)
(define tape (make-vector tapelength n))
(define i 0)
(call-with-current-continuation
(lambda (throw)
(define (put x) (if (< i tapelength)
(vector-set! tape i x) (throw 'ok)))
(define (get) (if (< i tapelength) (vector-ref tape i)
(throw 'ok)))
(define (r) (set! i (+ i 1)))
(define (l) (set! i (- i 1)))
(define (eraze) (put n))
(define (b)
(put e)(r)(put e)(r)(put 0)(r)(r)(put 0)(l)(l)(o))
(define (o) ;状態o
(let ((c (get)))
(if (= c 1) (begin (r)(put x)(l)(l)(l)(o))
(if (= c 0) (q)))))
(define (q) ;状態q
(let ((c (get)))
(if (or (= c 0) (= c 1)) (begin(r)(r)(q))
(begin (put 1)(l)(p)))))
(define (p) ;状態p
(let ((c (get)))
(if (= c x) (begin (eraze)(r)(q))
(if (= c e) (begin (r)(f))
(begin (l)(l)(p))))))
(define (f) 状態f
(let ((c (get)))
(if (or (= c 0) (= c 1)) (begin (r)(r)(f))
(begin (put 0)(l)(l)(o)))))
(b)))
(define (printtape) ;テープを文字列にする. (0 0 1 4 2 3)
(let ((t (vector->list tape))) ;=>"001 ex"
(display (list->string
(map (lambda (c)
(cond ((= c 4) #\space) ((= c 0) #\0)
((= c 1) #\1) ((= c 2) #\e)
((= c 1) #\1) ((= c 2) #\e)
((= c 3) #\x))) t)))))
最後のprinttapeは, 記号のリストを文字列に変換する. throwで飛び出した時のテープは
(printtape)
ee0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1x1x1x1 1 0 1 1
qで3つめの1を書こうとした時, 配列の範囲を飛び出したことが分かる.
さて, これを電卓プログラムに書き直す. 元の状態名には, 電卓プログラムでは使えない文字もあるので, b,o,q,p,fをそれぞれg,h,i,j,kとする. そして出来たプログラムは次のとおり. 最初のtはテープに相当する2つのスタックを用意する. スタックの底を示すため, -1を置く. スキャンするヘッドの下には, 空白を置く. rとlはヘッドを右や左に動かす. つまりrはU, lはNなのだが, 底を突き抜けないようなチェックが必要である. PやEもpやxとして実装した.
(1_"U4)t= ;Turing Machine Initialize
(U"4_G2_"G4E)r= ;Move Right
(N"4_G3_"GU4E)l= ;Move Left
(^)p= ;print a letter ap
(4p)x= ;erase print blank
状態b, o, q, p, fはそれぞれサブルーチンg, h, i, j, kとして, 定義する. セミコロンから右は, コメントである. プログラムの上の0や1やnoneは, その条件でジャンプする; またはジャンプからここに飛び込むというような, コメントである.
(2pr2pr0prr0pllh)g= ;b Pe,R,Pe,R,P0,R,R,P0,L,L ->o
; 1 0
("_5_Gi7_"Gr3plllh)h= ;o 1 R,Px,L,L,L -> o 0 ->q
; none none
("_1+7_Grri4_"G1plj)i= ;q 0 or 1 R,R -> q none P1,L ->p
; 01 e x01 e x
("2-c_G"3-d_G"4-d_Gllj9_"Grk3_"Gxri)j=
;p x E,R ->q e R ->f none L,L->p
; none
("_1+7_Grrk5_"G0pllh)k= ;f 0 or 1 R,R ->f none P0,L,L -> o
1を４個, その右に0を1個書いた直後のテープの状態(つまりスタック)は下のとおり.
(-1 2 2 0 4 0 4 1 4 0 4 1 4 1 4 0 4 1 4 1 4 1 4 0
4 1 4 1 4 1 4)(1 4 0 -1)
両端の-1はテープの終りだ. 左スタックの底には最初に書いたeeに相当する22が見える. その後, 空白を示す4を飛ばして読めば, 0010110111011110になっている. 0を書いてからヘッドが左へ2回動いたので, ヘッドの位置はスタックトップの1のところである.
分かってみると, Turingの元のプログラムを, 無駄がないのがよく分かった. また個人用電卓も, 2スタックモデルにすると, こんなことまで出来るということが見えた.
