Excel版チューリングマシン

VBA

Excel上で動かすチューリングマシンシミュレータを作ってみた。

使い方

B列に縦に65536マスのテープがあると想像する。
(横ではなくて縦にしたのは、横だと256マスしかないから）
その隣のA列をヘッドが現在の状態を表示しながら移動する。
チューリングマシンに対するプログラムはD列?H列に書く。
プログラムの書き方はgTuring風に、現在の状態(D列),テープ入力(E列),テープ出力(F列),ヘッド移動方向(G列),次の状態(H列)の順で指定する。
ただし、gTuringでは移動方向をlとrで表すけど、ここでは-1と1を使う。
また、gTuringでは_と書くところはセルに何も書かないことで表す。
1ステップずつ実行したい場合はstep()を、ちまちまやるのがめんどくさい場合はrun()を実行する

使用例

例として以下の2進数の加算をやってみる。

addbin.tur
こちらは２進数の加算です。 ２つの２進数を空白で区切って与えます。 例えば「10 11」(つまり 2 と 3) を与えると 「101」が答えになります。

http://www.mlb.co.jp/linux/science/gturing/index.html

ヘッド位置、テープ入力、プログラムを以下のように記入する。
(1行目のA,B,C…と1列目の1,2,3…はExcelの表示のつもり)

A B C D E F G H
1 ヘッド テープ 状態 入力 出力 移動 次状態
2 0 1 1 1 0
3 0 0 0 1 0
4 0 1 0 1 1
5 0 1 0 0 1 1
6 1 1 1 1 1
7 1 1 -1 2
8 1 2 0 1 -1 2
9 2 1 0 -1 4
10 2 1 3
11 3 1 1 3
12 3 0 1 3
13 4 1 1 -1 4
14 4 0 0 -1 4
15 4 -1 5
16 5 1 0 -1 5
17 5 1 1 0
18 5 0 1 1 0

動かしてみると、状態値が3でテープ値が(空欄)になって止まる。
テープ(B列)の状態が、1 0 1 (空欄) (空欄) (空欄) (空欄) になっているのでちゃんと計算しているようだ。

VBAコード本体

Sub step()
    x = [A1].End(xlDown).Row
    y = idx(Cells(x, 1) & "", Cells(x, 2) & "", 2)
    Cells(x, 1) = ""
    Cells(x, 2) = Cells(y, 6)
    Cells(x + Cells(y, 7), 1) = Cells(y, 8)
End Sub

Function idx(ByVal q, ByVal a, ByVal y)
    If IsEmpty(Cells(y, 4)) Then End
    If Cells(y, 4) & "" = q And Cells(y, 5) & "" = a Then idx = y Else idx = idx(q, a, y + 1)
End Function

Sub run()
    While True
        step
    Wend
End Sub

おぼえがき

普通のアセンブラではメモリの値をレジスタにコピー(ロード)、レジスタの値をメモリにコピー(ストア)とするけど、
チューリングマシンではテープの値を状態レジスタにロードとか、状態レジスタの値をテープにストアとかする命令はない。
むしろ状態レジスタはプログラムカウンタとしての役割も担っていて、次の状態の指定でgotoをやっている感じ。
しかし、この行が終わったら次の行という逐次処理はなくて、現在の状態とテープ参照値によって毎回if文を実行されている感じ。
Brainfuckでは1加算と1減算のみでメモリに好きな値は書き込めなかったが、チューリングマシンでは足し算等は出来ないがテープに好きな値が直接書き込める。
空欄のセルと0を比較するとTrueになってしまう。空欄のセル&""と0&""で比較するとFalseにできる。
とりあえずこれでExcel+VBAはチューリング完全であることが証明出来たことになるのかな？