概要
チューリングマシンを理解するために
https://www.amazon.co.jp/dp/4781912141
の付録にあるチューリングマシンシミュレータを使ってみます。
環境
MacOS High Sierra ver.10.13.2
準備の手順
以下をターミナルから1行ずつ実行するとなんとなく出来ます。
# 適当なディレクトリを作りワークスペースとする
mkdir work_turing
cd work_turing
# 全データをダウンロードする
wget http://www.saiensu.co.jp/book_support/978-4-7819-1214-1/turing.c
wget http://www.saiensu.co.jp/book_support/978-4-7819-1214-1/Suc
wget http://www.saiensu.co.jp/book_support/978-4-7819-1214-1/EQab
wget http://www.saiensu.co.jp/book_support/978-4-7819-1214-1/BB3
wget http://www.saiensu.co.jp/book_support/978-4-7819-1214-1/Runner
# 適当に中身を見てみる
cat Suc
cat EQab
cat BB3
cat Runner
# turing.cをコンパイル
gcc -o turing turing.c
# ls してみる->turingが出来ているはず
ls
# turingを実行可能にする
chmod +x turing
# これでturingシミュレータを動かす準備はできたはず
そもそもgccをインストールする
上記の手順でgccがインストールされていない場合はXCODEをインストールするのでも良さそうですが、下記のサイトを参考にHomebrewからインストールするほうが早いかも。
-
https://qiita.com/yoshizaki_kkgk/items/4663148a2b3ca078ddbc
- でHomebrewをインストール
-
brew install gccにてgccをインストール
Sucを見てみる
./turing < Suc
を実行すると
a --(0 0 R)--> a
a --(1 1 R)--> a
a --(. . L)--> b
b --(1 0 L)--> b
b --(0 1 N)--> c
b --(. 1 N)--> c
a: . . . . . . . . . .[1]0 1 1 . . . . . . . . . . . . . . . .
a: . . . . . . . . . . 1[0]1 1 . . . . . . . . . . . . . . . .
a: . . . . . . . . . . 1 0[1]1 . . . . . . . . . . . . . . . .
a: . . . . . . . . . . 1 0 1[1]. . . . . . . . . . . . . . . .
a: . . . . . . . . . . 1 0 1 1[.]. . . . . . . . . . . . . . .
b: . . . . . . . . . . 1 0 1[1]. . . . . . . . . . . . . . . .
b: . . . . . . . . . . 1 0[1]0 . . . . . . . . . . . . . . . .
b: . . . . . . . . . . 1[0]0 0 . . . . . . . . . . . . . . . .
c: . . . . . . . . . . 1[1]0 0 . . . . . . . . . . . . . . . .
プログラムの動き的には1011->1100となり、1０１１+1=1100という２進法の足し算的な動きになっている。多分
EQabを見てみる
./turing < EQab
を実行すると
1 --(. 1 N)--> F
1 --(X . R)--> 1
1 --(a . R)--> 2
1 --(b . R)--> 4
2 --(a a R)--> 2
2 --(X X R)--> 2
2 --(b X L)--> 3
2 --(. . L)--> Z
4 --(b b R)--> 4
4 --(X X R)--> 4
4 --(a X L)--> 3
4 --(. . L)--> Z
3 --(a a L)--> 3
3 --(b b L)--> 3
3 --(X X L)--> 3
3 --(. . R)--> 1
Z --(a . L)--> Z
Z --(b . L)--> Z
Z --(X . L)--> Z
Z --(. 0 N)--> F
1: . . . . . . . . . .[a]a b b b b a . . . . . . . . . . . . .
2: . . . . . . . . . . .[a]b b b b a . . . . . . . . . . . . .
2: . . . . . . . . . . . a[b]b b b a . . . . . . . . . . . . .
3: . . . . . . . . . . .[a]X b b b a . . . . . . . . . . . . .
3: . . . . . . . . . .[.]a X b b b a . . . . . . . . . . . . .
1: . . . . . . . . . . .[a]X b b b a . . . . . . . . . . . . .
2: . . . . . . . . . . . .[X]b b b a . . . . . . . . . . . . .
2: . . . . . . . . . . . . X[b]b b a . . . . . . . . . . . . .
3: . . . . . . . . . . . .[X]X b b a . . . . . . . . . . . . .
3: . . . . . . . . . . .[.]X X b b a . . . . . . . . . . . . .
1: . . . . . . . . . . . .[X]X b b a . . . . . . . . . . . . .
1: . . . . . . . . . . . . .[X]b b a . . . . . . . . . . . . .
1: . . . . . . . . . . . . . .[b]b a . . . . . . . . . . . . .
4: . . . . . . . . . . . . . . .[b]a . . . . . . . . . . . . .
4: . . . . . . . . . . . . . . . b[a]. . . . . . . . . . . . .
3: . . . . . . . . . . . . . . .[b]X . . . . . . . . . . . . .
3: . . . . . . . . . . . . . .[.]b X . . . . . . . . . . . . .
1: . . . . . . . . . . . . . . .[b]X . . . . . . . . . . . . .
4: . . . . . . . . . . . . . . . .[X]. . . . . . . . . . . . .
4: . . . . . . . . . . . . . . . . X[.]. . . . . . . . . . . .
Z: . . . . . . . . . . . . . . . .[X]. . . . . . . . . . . . .
Z: . . . . . . . . . . . . . . .[.]. . . . . . . . . . . . . .
F: . . . . . . . . . . . . . . .[0]. . . . . . . . . . . . . .
よくわからない。。。
BB3を見てみる
./turing < BB3
を実行すると
1 --(. X R)--> 2
1 --(X X L)--> 3
2 --(. X L)--> 1
2 --(X X R)--> 2
3 --(. X L)--> 2
3 --(X X N)--> F
1: . . . . . . . . . .[.]. . . . . . . . . . . . . . . . . . .
2: . . . . . . . . . . X[.]. . . . . . . . . . . . . . . . . .
1: . . . . . . . . . .[X]X . . . . . . . . . . . . . . . . . .
3: . . . . . . . . .[.]X X . . . . . . . . . . . . . . . . . .
2: . . . . . . . .[.]X X X . . . . . . . . . . . . . . . . . .
1: . . . . . . .[.]X X X X . . . . . . . . . . . . . . . . . .
2: . . . . . . . X[X]X X X . . . . . . . . . . . . . . . . . .
2: . . . . . . . X X[X]X X . . . . . . . . . . . . . . . . . .
2: . . . . . . . X X X[X]X . . . . . . . . . . . . . . . . . .
2: . . . . . . . X X X X[X]. . . . . . . . . . . . . . . . . .
2: . . . . . . . X X X X X[.]. . . . . . . . . . . . . . . . .
1: . . . . . . . X X X X[X]X . . . . . . . . . . . . . . . . .
3: . . . . . . . X X X[X]X X . . . . . . . . . . . . . . . . .
F: . . . . . . . X X X[X]X X . . . . . . . . . . . . . . . . .
ビジービーバーというものらしい。全然知らないけど。
https://en.wikipedia.org/wiki/Turing_machine_examples#3-state_Busy_Beaver
のほうが詳しい。
Runnerを見てみる
./turing < Runner
を実行すると
R --(a a R)--> a
R --(b b R)--> b
a --(a a R)--> a
a --(b a R)--> a
a --(. a R)--> a
b --(a b R)--> b
b --(b b R)--> b
b --(. b R)--> b
R: . . . . . . . . . .[a]b b b a a b . . . . . . . . . . . . .
a: . . . . . . . . . . a[b]b b a a b . . . . . . . . . . . . .
a: . . . . . . . . . . a a[b]b a a b . . . . . . . . . . . . .
a: . . . . . . . . . . a a a[b]a a b . . . . . . . . . . . . .
a: . . . . . . . . . . a a a a[a]a b . . . . . . . . . . . . .
a: . . . . . . . . . . a a a a a[a]b . . . . . . . . . . . . .
a: . . . . . . . . . . a a a a a a[b]. . . . . . . . . . . . .
a: . . . . . . . . . . a a a a a a a[.]. . . . . . . . . . . .
a: . . . . . . . . . . a a a a a a a a[.]. . . . . . . . . . .
a: . . . . . . . . . . a a a a a a a a a[.]. . . . . . . . . .
a: . . . . . . . . . . a a a a a a a a a a[.]. . . . . . . . .
a: . . . . . . . . . . a a a a a a a a a a a[.]. . . . . . . .
a: . . . . . . . . . . a a a a a a a a a a a a[.]. . . . . . .
a: . . . . . . . . . . a a a a a a a a a a a a a[.]. . . . . .
a: . . . . . . . . . . a a a a a a a a a a a a a a[.]. . . . .
a: . . . . . . . . . . a a a a a a a a a a a a a a a[.]. . . .
a: . . . . . . . . . . a a a a a a a a a a a a a a a a[.]. . .
a: . . . . . . . . . . a a a a a a a a a a a a a a a a a[.]. .
a: . . . . . . . . . . a a a a a a a a a a a a a a a a a a[.].
a: . . . . . . . . . . a a a a a a a a a a a a a a a a a a a[.]
Out of tape.
自分で考えて機能を作ってみる
下記のようなファイルを置きます。
下記の内容をコピーして、
cat > test.txtを実行し、直後にペースト、そしてCtrl+Cを実行します。
test.txt
{
1 0 0 R 1
1 1 1 R 2
1 . 0 N F
2 0 0 R 2
2 1 1 R 1
2 . 1 N F
}
<11000111>
そして
./turing < test.txt
実行すると。。。
1 --(0 0 R)--> 1
1 --(1 1 R)--> 2
1 --(. 0 N)--> F
2 --(0 0 R)--> 2
2 --(1 1 R)--> 1
2 --(. 1 N)--> F
1: . . . . . . . . . .[1]1 0 0 0 1 1 1 . . . . . . . . . . . .
2: . . . . . . . . . . 1[1]0 0 0 1 1 1 . . . . . . . . . . . .
1: . . . . . . . . . . 1 1[0]0 0 1 1 1 . . . . . . . . . . . .
1: . . . . . . . . . . 1 1 0[0]0 1 1 1 . . . . . . . . . . . .
1: . . . . . . . . . . 1 1 0 0[0]1 1 1 . . . . . . . . . . . .
1: . . . . . . . . . . 1 1 0 0 0[1]1 1 . . . . . . . . . . . .
2: . . . . . . . . . . 1 1 0 0 0 1[1]1 . . . . . . . . . . . .
1: . . . . . . . . . . 1 1 0 0 0 1 1[1]. . . . . . . . . . . .
2: . . . . . . . . . . 1 1 0 0 0 1 1 1[.]. . . . . . . . . . .
F: . . . . . . . . . . 1 1 0 0 0 1 1 1[1]. . . . . . . . . . .
こんな感じで１の数を必ず偶数にしてくれます。
パリティビットの付加のようなことが出来ました。
感想
学生時代にやったようなきがするチューリングマシンを思い出しました。