チューリングマシンを動かしてみる

# 概要

チューリングマシンを理解するために
https://www.amazon.co.jp/dp/4781912141
の付録にあるチューリングマシンシミュレータを使ってみます。

## 環境
MacOS High Sierra ver.10.13.2

# 準備の手順
以下をターミナルから1行ずつ実行するとなんとなく出来ます。

```shell
# 適当なディレクトリを作りワークスペースとする
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を見てみる

```shell
./turing < Suc
```

を実行すると

```shell:

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を見てみる

```shell
./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を見てみる

```shell
./turing < BB3
```

を実行すると

```shell:
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://ja.wikipedia.org/wiki/%E3%83%93%E3%82%B8%E3%83%BC%E3%83%93%E3%83%BC%E3%83%90%E3%83%BC)というものらしい。全然知らないけど。
https://en.wikipedia.org/wiki/Turing_machine_examples#3-state_Busy_Beaver
のほうが詳しい。

## Runnerを見てみる

```shell
./turing < Runner
```

を実行すると

```shell:
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を実行します。 

```shell: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>

```
そして

```shell
./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]. . . . . . . . . . . 
```

こんな感じで１の数を必ず偶数にしてくれます。
[パリティビット](https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%AA%E3%83%86%E3%82%A3%E3%83%93%E3%83%83%E3%83%88)の付加のようなことが出来ました。

# 感想

学生時代にやったようなきがするチューリングマシンを思い出しました。