チューリングマシンで掛け算
ActionScriptの勉強がてら簡単なものを実装してみました。
元ネタは 計算理論 (チューリングオムニバス―コンピュータサイエンスの旅) に載っていた内容で、単進法（数mはm個の連続する"1"の列で表現。例：3 => "111"）表記での掛け算です。
具体的には、
1111x111 # 4 x 3 ↓ 111111111111 # 12
のように変換するプログラム。
この本ではこの掛け算のプログラムを五項組（現在の状態、現在のテープの記号、次に遷移する状態、現在のテープに印字する記号、次に移動する方向）の集合で表しています。書き写すのが面倒なので、実装したコードで表すと
statBox.add( 0, " ", 0, " ", "R");
statBox.add( 0, "1", 1, "1", "L");
statBox.add( 1, " ", 2, "*", "R");
statBox.add( 2, " ", 3, " ", "L");
statBox.add( 2, "*", 2, "*", "R");
statBox.add( 2, "1", 2, "1", "R");
statBox.add( 2, "x", 2, "x", "R");
statBox.add( 2, "A", 2, "A", "R");
// statBox.add( 3, "1", 9, " ", "L");
statBox.add( 3, "1", 4, " ", "L");
statBox.add( 3, "x", 9, "x", "L");
statBox.add( 4, "1", 4, "1", "L");
statBox.add( 4, "x", 5, "x", "L");
statBox.add( 5, "*", 8, "*", "R");
statBox.add( 5, "1", 6, "A", "L");
statBox.add( 5, "A", 5, "A", "L");
statBox.add( 6, " ", 7, "1", "R");
statBox.add( 6, "*", 6, "*", "L");
statBox.add( 6, "1", 6, "1", "L");
statBox.add( 7, "*", 7, "*", "R");
statBox.add( 7, "1", 7, "1", "R");
statBox.add( 7, "x", 5, "x", "L");
statBox.add( 7, "A", 7, "A", "R");
statBox.add( 8, " ", 3, " ", "L");
statBox.add( 8, "1", 8, "1", "R");
statBox.add( 8, "x", 8, "x", "R");
statBox.add( 8, "A", 8, "1", "R");
// statBox.add( 9, "*", 10, " ", "S");
statBox.add( 9, "*", 10, " ", "R");
statBox.add( 9, "1", 9, "1", "L");
// statBox.add( 9, "x", 9, "x", "L");
statBox.add(10, " ", 11, " ", "L");
statBox.add(10, "1", 10, " ", "R");
statBox.add(10, "x", 10, " ", "R");
statBox.add(11, " ", 11, " ", "L");
statBox.add(11, "1", 12, "1", "L");
statBox.add(12, "1", 12, "1", "L");
statBox.add(12, " ", 13, " ", "S");となります。
「現在の状態（0から開始）と現在のテープの記号」を元に決定された「状態遷移とテープへのアクション（印字と移動）」を行い、また状態とテープの記号をみて… を繰り替えしていくといつの間にか掛け算が出来ていて幸せ、というしろものです。
ちなみに、コメントアウトしているところは、どうやら本の内容が上手くないらしいので修正して見たところです（状態遷移図も載っていたのでそれを参考にデバッグ）。
コンパイルしてswfファイルになっているので、はてなには置けずにFC2の物置（でアクセス制限が掛かっていたので）自鯖に置いてあります -> TuringMachine.swf。
掛け合わせたい数と動作スピードを入力して、「かけざん開始」とかいうのをクリックするとプログラムが動き始めます。
このチューリングマシンの動作概要について簡単に補足しておきます（動かしてみてやっと分かった…）。
- 左端に作業用のしきりである「*」をおいておく（これの左側が計算結果となる）
- 掛け算の右項の数分、左項の「1」の列を「*」の左側に一つ一つ書き写す。その度、右項の「1」は消去していく
- 2でどこまで書き写したか判断できるよう、書き写したところは「A」に変えておく
- 2が終わったら3の「A」は「1」に戻しておく
- 全部書き写して（＝右項がなくなる）「*」の左側に掛け算の結果が出来あがったら、余計な文字を消していく
- そのままだと掛け算の結果が見えないので、左側に移動する
一番最後は、苦肉の策として私が勝手に付け足したものです。最初は五項組のプログラムを見てもちんぷんかんぷんだったのですが、デバッグを繰り替えすうちに、何だかプログラムが組めるようになってきました（プログラミングスキルの向上にはデバッグを！）。
あと、勢いで初githubしてみました -> komamitsu/turing_machine_as3 · GitHub。本当はView的なところは、mxmlに切り出した方が良いかと思いますが、まぁ、ちからつきた（飽きてきた）ということで…
いきなりswfファイルなんて開けるか！というセキュリティ意識の高いかたはコードに目を通してからコンパイルしてみるもの良いかと思います。全然たいしたものでは無いですけれども。
ActionScriptで無名関数が使えたのはちょっとした発見。あと、ActionScriptだけだとボタンが劇的に書きづらいのは気のせいかしら…
ちなみに、Linux & Firefox（Adobe Flash Player 10）の組み合わせでしか動作確認していませんので、他の環境で何かあったらごめんなさい。
