menu
書いてる野郎
orebike@gmail.com
数学 / チューリングマシン
数学 / チューリングマシン
アルゴリズムで解けない問題が存在するということを証明するために作られた、何でも計算できる(予定の)機械。 この機械で解けない問題を発見(証明)できれば、そのような問題が存在するという証明になる。
目的は、計算不可能な問題が存在するという証明であったが、チューリングマシンは、それが「計算するとは？」、「考えるとは？」という疑問に繋がっていき、 コンピュータや人工知能の発展に繋がっていった。
チューリングマシンは人間の思考を真似る機械。
色々なサイトや本の説明を読むと、単純な仕組みで現代のコンピュータの基本的な原理を説明できるという話になっているのだが、 その説明が数学のゴチャゴチャした話になっているのでなんだか実感がつかみにくいのでまとめる。
コンセプトは、計算可能という性質(計算できるかできないか)が定義できるなら、それを物凄い量積み上げればどんな計算でもできるということ。
基本
ヘッドとテープからなる機械。
- ヘッド
- テープの上を移動できる
- ヘッドの位置のテープに情報を書き込める(123 等)
- ヘッドの位置のテープの情報を読み取れる
- 内部状態を保持できる
- 読み取ったテープ情報に基づいてヘッドを動作(読む、移動する、内部状態を変える、書く)させるアルゴリズム(行動パターンの表のようなもの)を内蔵している
- テープ
- 無限の長さがある
アルゴリズムの複雑さはそのパターンの量が多くなる、テープに書き込む情報が複雑になると考えればよい。 問題を単純化しているなら、アルゴリズムは少なく動作は多くなり、問題が複雑なら、アルゴリズムは多く、動作は少なくなる
このヘッド内のアルゴリズムをうまく作ってやることによって計算結果がテープに現れるという仕組みになっている。
1を足すチューリングマシン
非常に単純化するため、単に10進法である数字に1を足すチューリングマシンを考える。
初期状態: 位置一の位のセル上、内部状態計算中
| 入力(テープから) | 現在の内部状態 | → | 行動(書き込み) | 内部状態変化 | 行動(移動) | memo |
|---|---|---|---|---|---|---|
| 0 | 計算中 | → | 1 を書き込む | 計算終了 | 動かず | |
| 1 | 計算中 | → | 2 を書き込む | 計算終了 | 動かず | |
| … | … | → | … | … | … | |
| 8 | 計算中 | → | 9 を書き込む | 計算終了 | 動かず | |
| 9 | 計算中 | → | 0 を書き込む | 計算中 | 左(次の桁)に移動 | |
| 空白 | 計算中 | → | 1 を書き込む | 計算終了 | 動かず | |
| なんでも | 計算終了 | → | 書かない | 計算終了(変化しない) | 動かず | |
実際にチューリングマシンを作るとわかるが、2020年現在、日本の小学校で教えているプログラミング教育ではこういう問題が結構ある。 つまり、それはアルゴリズムの本質をついているということである。
初期位置はこうなる
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 中 | |||||
| tape | 3 | 1 | 2 |
↑で入力は2になり内部状態は計算中であるので3を書き込んで内部状態を計算終了
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 終 | |||||
| tape | 3 | 1 | 3 |
内部状態が計算終了になったので後は何がおきても変化しない。
桁を考えてみる。
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 中 | |||||
| tape | 3 | 1 | 9 |
↑で入力は 9 になり内部状態は計算中であるので 0 を書き込む。内部状態は計算中を維持し、左に移動する。
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 中 | |||||
| tape | 3 | 1 | 0 |
↑で入力は 1 になり内部状態は計算中であるので 2 を書き込んで内部状態を計算終了
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 終 | |||||
| tape | 3 | 2 | 0 |
桁が増えるを考えてみる
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 中 | |||||
| tape | 9 | 9 | 9 |
↑で入力は 9 になり内部状態は計算中であるので 0 を書き込む。内部状態は計算中を維持し、左に移動する。
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 中 | |||||
| tape | 9 | 9 | 0 |
↑で入力は 9 になり内部状態は計算中であるので 0 を書き込む。内部状態は計算中を維持し、左に移動する。
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 中 | |||||
| tape | 9 | 0 | 0 |
↑で入力は 9 になり内部状態は計算中であるので 0 を書き込む。内部状態は計算中を維持し、左に移動する。
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 中 | |||||
| tape | 0 | 0 | 0 |
↑で入力は「空白」になり内部状態は計算中であるので 1 を書き込んで内部状態を計算終了
| pos | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| head | 終 | |||||
| tape | 1 | 0 | 0 | 0 |
計算が有限個のパターンの組み合わせとして表現できる可能性が感じられる。
つまり、計算するとはこのパターンを用意すると同じになる。 パターンを考えて用意しなければならないのだが、有限個のパターンの組み合わせであるのだから、何かの問題を解くアルゴリズムは有限個のパターンになるはずである。
このパターンを限りなく少なくしたのが、コンピュータで使う2進数だということだ。 今は10進数で計算したが、別にこれを2進数にしても問題ない。使うテープの量は増えるが、パターンは単純化する。
2つの値が同じか判断するチューリングマシン
10進法である数字2つを足すチューリングマシン
このように空白で区切られた2つの数字 42 と 42 が等しいか判断するチューリングマシンを考えてみる
| pos | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| head | 中 | ||||||
| tape | 4 | 2 | 4 | 2 |
全桁一致を考えればいいすればいい。 なので考えることは、2つの数字の同じ桁をいったり来たりすることだけである。
2つの値を足すチューリングマシン
同じになるまで1を足せばいいのだから、↑の2つの組み合わせで作ることができる。
万能チューリングマシン
チューリングマシンにある特定の計算をするアルゴリズム(パターン)を与えれば計算ができるということはなんとなく感じられた。
なので、そのパターンを作るためのパターン(テープとヘッドのルール)をチューリングマシンに教えて、その結果をチューリングマシンに入力すれば、あらゆる計算が可能になるチューリングマシンになる。 このチューリングマシンのことを万能チューリングマシンと呼ぶ。
このような万能チューリングマシンの能力(任意のチューリングマシンを作れる能力)のことを「チューリング完全」と呼ぶ。
現代のプログラミングはプログラミング言語で文法や機能は言語によって違うが、アルゴリズムを記述することによりあらゆる計算ができるようになっている。 つまりそれはプログラミング言語によってチューリングマシンを記述しているという意味であり、それは「チューリング完全」であるということになる。
※実際の実装では無限のメモリや無限のCPUを用意できないので、制約はある。言語仕様は実装の制約を織り込むモノなので「〇〇言語は完全にチューリング完全」という話はそもそも議論する意味が無い。
当然ながら、万能チューリングマシンを作ることができる万能万能チューリングマシンも「チューリング完全」であるという。 チューリング完全であるとは思えないような非常に単純な機械(処理系)もチューリング完全であることがわかっていて、 その別の機械でその単純な機械を模倣できることを確かめることによってその機械がチューリング完全であることが確認できる。
初期のコンピュータがある特定の計算をするために回路を作っていたのに対し、現代のコンピュータはプログラミングすることにより様々な計算ができるようになっているのは、このチューリングマシンの関係と似ている。
