チューリングマシンのシュミレーターを作ってみた[42Tokyo]

## はじめに

42の課題で、チューリングマシンとそのシュミレーターを、ペアと一緒に二人で作成したため、その備忘録として書いています。

課題全体の解説というわけではない点についてはご了承ください。

作成したものはこちらにあります。

https://github.com/corvvs/turrrr

また42の他の活動についてはこちらにありますので、42自体に興味がある方はぜひこちらもどうぞ。

https://note.com/kotabrog/n/n292c0b5ef071

ちなみに前回解いた課題の記事はこちらになります。

https://qiita.com/Kotabrog/items/f4bacd71e6a289e40ece

## 作ったもの

ということで作ったものですが、以下のようなものになります！

![img](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533384/c9048acd-6ceb-9b06-a691-7a6ec64f9271.png)

これは以下のコマンドで出力されたものです。

```
./ft_turing json/unary_add.json "111+11="
```

unary_add.jsonというjsonファイルと、"111+11="というチューリングマシンの入力であるテープを受け取って、計算を行うというものになります。

unary_add.jsonは、"111+11="を"11111"のように単純に足し合わせるチューリングマシンの設定ファイルで、それをft_turingでシュミレーションしているという感じになります。

## チューリングマシンって？

wikipediaにはこんな感じで書いてあります。

> チューリングマシンには、いわゆるハードウェアに相当するものとして、
>
>- その表面に記号を読み書きできるテープ。長さは無制限（必要になれば順番にいくらでも先にシークできる[注 1]）とする
>- テープに記号を読み書きするヘッド
>- ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトン
>
>がある。
>
>また、ソフトウェアに相当するものとして、以下がある。
>
>- テープに読み書きされる有限個の種類の記号
>- 最初から（初期状態において）テープにあらかじめ書かれている記号列
>- 有限オートマトンの状態遷移規則群。詳細は次で述べる
>
>この有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」（内部状態）と、ヘッドがテープの「現在の場所」から読み>出した記号の組み合わせに応じて、次のような動作を実行する。
>
>- テープの「現在の場所」に新しい記号を書き込む（あるいは、現在の記号をそのままにしてもよい）
>- ヘッドを右か左に一つシークする（あるいは、移動しなくてもよい）
>- 有限オートマトンを次の状態に状態遷移させる（同じ状態に遷移してもよい）

https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3

ここからは今回の課題用の独自設定もあるので、一般的なチューリングマシンではない部分もあることをお気を付けください。

チューリングマシンには、"111+11="のような「テープ」と、今"="を読みにいっています！みたいな「状態」と、今見ている場所である「ヘッド」があります。

チューリングマシンの1ステップは以下のようになっています。

- ヘッドの位置の文字と、今の状態を確認する
- その文字と状態に対応する遷移規則を確認する
- ヘッドの文字を、遷移規則に書いてある文字に書き換える
- 今の状態を遷遷移規則に書いてある状態に書き換える
- ヘッドの位置を遷移規則に書いてある方法に従って移動する（今回の課題だと左右のみ）

これを繰り返すことで、チューリングマシンでは、現代で使用されているパソコンのように、いろいろなプログラムを動かすことができます。

## チューリングマシンの設定ファイル

今回の課題では、このチューリングマシンを、jsonファイルで設定しています。

つまり、このjsonファイルが、プログラムのようなものになります。

```json
{
	"name" : "unary_add",
	"alphabet": [ "1", ".", "+", "=" ],
	"blank" : ".",
	"states" : [ "scanright", "eraseone", "HALT" ],
	"initial" : "scanright",
	"finals" : [ "HALT" ],
	"transitions" : {
	"scanright": [
	{ "read" : "1", "to_state": "scanright", "write": "1", "action": "RIGHT"},
	{ "read" : "+", "to_state": "scanright", "write": "1", "action": "RIGHT"},
	{ "read" : "=", "to_state": "eraseone" , "write": ".", "action": "LEFT" }
	],
	"eraseone": [
	{ "read" : "1", "to_state": "HALT", "write": ".", "action": "RIGHT"}
	]
	}
}

```

各項目については以下のようになってます。

- name：プログラムの名前
- alphabet：テープに使える文字
- blank：空白文字。最初のテープには含められない
- states：状態のリスト
- initial：最初の状態
- finals：最後の状態のリスト。このいずれかになったら、終了
- transitions：各状態とヘッドの位置に対応する遷移先の規則

ということで、用語みたいなもののご説明ができたので改めてですが、今回の課題では、以下のものを作成しました。

- この設定ファイルと、テープを受け取ってチューリングマシンをシュミレーションするプログラム
- いくつかのチューリングマシンの設定ファイル

## シュミレーションするプログラム

シュミレーションするプログラムは、OCamlという言語で作成しました。

OCamlの説明については省略します。

## 作ったチューリングマシン

今回作ったチューリングマシンの設定ファイルは以下の5つになります。

- 加算：111+11= -> 11111
- 回文判定機：abcba -> abcbay (テープの右側にyがあるとyes、nがあるとnoという意味)
- 0^n1^nの形になっているか判定機：00011111 -> 00011111y
- 0が偶数個か判定機：000000 -> 000000y
- 加算をするチューリングマシンを作るチューリングマシン："[>A1A1R>A+A1R>A=B.L>B1H.R]111+11="->"[>A1A1R>A+A1R>A=B.L>B1H.R]11111"

最後のものは、`[>A1A1R>A+A1R>A=B.L>B1H.R]`の部分が、jsonファイルで設定していたチューリングマシンの遷移先の規則になっていて、まさにチューリングマシンを作るチューリングマシンという感じになっています。

## 参考資料

今回はチューリングマシンについてなどいろいろと調べたので、まとめておきます。

https://zenn.dev/airev/articles/airev-quantum-03

https://www.eidos.ic.i.u-tokyo.ac.jp/~alumni/liquid/notes/computation.pdf

https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0

http://edu.net.c.dendai.ac.jp/algorithm/2015/3/index.xhtml

http://web.sfc.keio.ac.jp/~hagino/mi17/05.pdf

http://www.akita-pu.ac.jp/system/elect/ins/kusakari/japanese/teaching/InfoMath/2007/note/5.pdf

https://www.hirasa.mgmt.waseda.ac.jp/lab/imc.pdf

## おわりに

今回は何を作ったかのご紹介とリンク集という感じになりました。

今回あまり触れませんでしたが、計算量とかの話でチューリングマシンについて考えるようで、そのへんの話も調べたりしたので、リンクにあったりします。