2009年9月10日木曜日

個人用電卓のプログラミング

今年の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を4個, その右に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スタックモデルにすると, こんなことまで出来るということが見えた.

2009年9月7日月曜日

Dudeneyのパズル

Tne New Martin Gardner Mathematical Libraryの2冊目を読んでいたら, Dudeneyのパズルというのに出会った.

正三角形を4つのピースに切り分け, 再配置して正方形を作れ. 難問である. この本は同時に解答を示しているが, それでよい理由はそう自明ではない.

まず解答は次の通り. 正三角形ABCの辺ABに中点D, BCに中点Eをとる. AEをEの方向にEBの長さだけ延長しFとする. AFの中点Gを中心に半径GFの円を描き, CBのBの方向への延長上との交点をHとする. Eを中心に半径EHの円を描き, ACとの交点をJとする. AC上にBEに等しくJKをとる. DとKからJEに下ろした垂線の足をそれぞれLとMとする.

正三角形ABCをJE, DL, KMで切り分け, 再配置すると, 同面積の正方形が得られる.



元の正三角形の1辺の長さを2とする. 三角形の高さは√3なので, 正三角形の面積も√3である. 従って同面積の正方形の1辺の長さは√√3である.

上の作り方で出来た正方形の1辺は√√3であろうか.

正三角形の1辺の長さを2とし, 作り方の図で考えると, AE=√3, AF=√3+1, ∴AG=GF=(√3+1)/2, GE=√3-(√3+1)/2=(√3-1)/2. GEHにおいて, EH=√(GH^2-GE^2) =√((√3+1)^2/4)-(√3-1)^2/4)) =√((3+2√3+1)/4-(3-2√3+1)/4)=√√3=EJ. これが作るべき正方形の1辺である.

Eから辺ACに下ろした垂線の足をNとする. EN=(√3)/2. 三角形JENと三角形JKMは相似で斜辺から比は√√3:1. KM=√3/2/√√3=(√√3)/2. つまり正方形の1辺の半分である.

ところで三角形EDLも, DE=JK(=1)だから, JKMと合同である. DL=(√√3)/2.

従って正方形の上と下の辺はLD+LD=MK+MK=√√3.

左の縦の辺は, LE=MJだから, LE+EM=MJ+EM=EJ=√√3. 右の縦の辺も同様. 従って正三角形と同面積の正方形が得られた.

なるほど.
ところで
√√3=1.31607,
A=(0,0), B=(1,√3), C=(2,0), D=(1/2,√3/2), E(3/2,√3/2), JN=√(√3-3/4), AJ=AN-JNなので J=(3/2-JN,0), K=(5/2-JN,0), ∠EJN=atan(EN,JK)=41.15゜
である. NとKはほとんど同じ位置だが, JN=0.99098ゆえ, Kの方がわずかに右にある.

2009年9月2日水曜日

中西式置換プログラム

前回のブログ(2009年8月27日中西流置換プログラム)の最後に書いたTAOCPのアルゴリズム7.2.1.2-Lは, Lというだけあって辞書式順(lexicographicalorder)で, n項の置換, 例えば(1 2 2 3)の置換

((1 2 2 3) (1 2 3 2) (1 3 2 2) (2 1 2 3) (2 1 3 2) (2 2 1 3)
(2 2 3 1) (2 3 1 2) (2 3 2 1) (3 1 2 2) (3 2 1 2) (3 2 2 1))

を作る. 辞書式順とは, 配列の左端に小数点があるとして, 数値順にソートするものである.

(0 1 2 3)の中西ソートの結果

(perm '(0 1 2 3)) =>
((0 1 2 3) (1 0 2 3) (1 2 0 3) (1 2 3 0) (0 2 1 3) (2 0 1 3)
(2 1 0 3) (2 1 3 0) (0 2 3 1) (2 0 3 1) (2 3 0 1) (2 3 1 0)
(0 1 3 2) (1 0 3 2) (1 3 0 2) (1 3 2 0) (0 3 1 2) (3 0 1 2)
(3 1 0 2) (3 1 2 0) (0 3 2 1) (3 0 2 1) (3 2 0 1) (3 2 1 0))



(define (dec s)
(string->number (string-append "."
(apply string-append (map number->string s)))))

で小数にする.

(dec '(0 1 2 3)) => .0123


先ほどの置換を小数にしてソートすると

(sort (map dec (perm '(0 1 2 3))) <) =>
(.0123 .0132 .0213 .0231 .0312 .0321 .1023 .1032 .1203 .123
.1302 .132 .2013 .2031 .2103 .213 .2301 .231 .3012 .3021
.3102 .312 .3201 .321)


アルゴリズムLの結果の辞書式順
 
                                                                    
(algorithm7212l '(0 1 2 3))=>
((0 1 2 3) (0 1 3 2) (0 2 1 3) (0 2 3 1) (0 3 1 2) (0 3 2 1)
(1 0 2 3) (1 0 3 2) (1 2 0 3) (1 2 3 0) (1 3 0 2) (1 3 2 0)
(2 0 1 3) (2 0 3 1) (2 1 0 3) (2 1 3 0) (2 3 0 1) (2 3 1 0)
(3 0 1 2) (3 0 2 1) (3 1 0 2) (3 1 2 0) (3 2 0 1) (3 2 1 0))

になる. いまはどれも4桁なので, 小数ではなく, 整数と思ってソートするのでもよい.

私のブログの2008年10月28日のに, 切頭八面体の絵があり, {0,1,2,3}の全順列を, 隣り同士の交換で実現したと書いてある. 隣り同士の交換で, 全順列を作るのを, 英語ではPlain Changeという.

下の図がその1例である. 左の24段が, {0,1,2,3}の置換で, x印のところが隣り同士交換した場所である. 一番下のx印の交換をすると, 一番上に戻る.

右上の6段は, 左で0を挿入される{1,2,3}の置換である. これも同じように出来ている.

赤線は0の移動を示す.




x印が連続するように, 中西アルゴリズムを少し修正すると,plain changeのアルゴリズムになる. 前回のプログラムのappendを1つおきに逆にappendするようにすればよい. それが下のrevap (reverse appendのつもり)

(revap '(0 1) '(2 3) '(4 5) '(6 7)) => (0 1 3 2 4 5 7 6)

これを使うとplain changeが出来る.

(define (plainchange ls)
(define (revap . ls)
(cond ((null? ls) '())
((null? (cdr ls)) (car ls))
(else (append (car ls) (reverse (cadr ls))
(apply revap (cddr ls))))))
(define (ins h tl)
(if (null? tl) (list (list h))
(cons (cons h tl)
(map (lambda (l) (cons (car tl) l)) (ins h (cdr tl))))))
(if (null? ls) (list '())
(apply revap (map (lambda (l) (ins (car ls) l))
(plainchange (cdr ls))))))

(plainchange '(0 1 2 3))の結果を切頭八面体のHamiltonian閉路にしたのが



である.