チューリングマシン解説
電子計算機がまだ存在しなかった1936年、24歳の数学者アラン・チューリングは、計算が機械的であるとはどういうことかを問いました。彼の答えは、これ以上できることを減らしようがないほど単純な架空の機械でした。決まった規則表に従い、テープの上で1セルずつ記号を読み書きするだけです。この機械こそが計算そのものを定義することになり、さらに、どんなコンピューターにも決して答えられない問いがあることを示しました。
チューリングの問い
1928年、ダフィット・ヒルベルトは、数学のあらゆる命題について、それが証明できるかどうかを判定する機械的な手続きが存在するかを問いました。これが決定問題(Entscheidungsproblem)です。これに答えるには、機械的な手続きとは何かを誰かが正確に述べなければなりませんでした。1936年の論文「計算可能数について」(On Computable Numbers)で、チューリングは鉛筆と紙で作業する計算係を思い描き、その作業を最小のステップにまで切り詰めました。1つの記号を見る、それを書き換える、隣の記号へ移る、そして自分が何をしていたかを少しだけ覚えておく。その結果がチューリングマシンです。
機械
チューリングマシンには、セルに区切られた、両方向に無限に続くテープがあり、各セルには記号が1つ入っています。たいていは空白です。ヘッドはセルの1つの上にあり、機械は有限個の状態のうちの1つにあります。規則表は、各状態とヘッドが読みうる各記号について、書く記号、動く方向、次の状態を与えます。機械は1ステップに1つの規則を適用します。停止状態に入ると止まり、テープに残ったものがその答えになります。
規則表としてのプログラム
規則表の一つひとつがプログラムです。2進数に1を足すには、機械は数の右端まで進み、それから左へ動きながら 1 を 0 に変えていき、0 か空白が見つかったらそれを 1 にします。単語が回文かどうかを調べるには、最初の記号を消して状態の中に覚えておき、反対の端まで走って最後の記号が一致するかを確かめ、これを繰り返します。掛け算や並べ替えをするような長いプログラムも、同じ数種類の規則から組み立てられます。
万能機械
チューリングの最も重要なアイデアは、規則表そのものをテープに書けるということでした。万能チューリングマシンは、ほかの任意の機械の記述とその入力を読み、それを1ステップずつ模倣します。したがって、1台の決まった機械であらゆるプログラムを実行できます。これは、ソフトウェアがメモリ上のデータにすぎないプログラム内蔵方式のコンピューターすべての背後にある原理です。万能チューリングマシンを模倣できるシステムはチューリング完全と呼ばれ、あらゆるプログラミング言語、コンウェイのライフゲーム、セルオートマトンのルール110などがこれに当たります。
チャーチ=チューリングのテーゼ
同じ年、アロンゾ・チャーチはラムダ計算によって計算を記述し、2つの定義はまったく同じ関数を計算できることがわかりました。レジスタマシンから現代のプロセッサーまで、その後のあらゆるモデルも同様でした。チャーチ=チューリングのテーゼは、段階的な手続きで計算できるものは何でもチューリングマシンで計算できると述べます。「段階的な手続き」は形式化されていない概念なのでこれは証明できませんが、反例はこれまで一度も見つかっていません。
停止性問題
チューリングは次に、機械的な答えのない問いがあることを示しました。あらゆるプログラムと入力について、そのプログラムがいずれ停止するかどうかを判定できる機械があったとします。この判定器に自分自身について問い合わせ、その逆を行う新しいプログラムを作ります。停止すると言われたら永遠にループし、ループすると言われたら停止するのです。どちらの答えも誤りになるので、そのような判定器は存在しえません。停止性問題は決定不能であり、それとともに決定問題も決定不能です。あらゆる数学的な問いに決着をつけられるアルゴリズムはないのです。
ビジービーバー
1962年、ティボール・ラドーは停止性問題をゲームに変えました。n 個の状態と記号 0 と 1 を持ち、空白のテープから始めると停止する機械すべての中で、最も多くの 1 を書くのはどれか、そしてそのような機械は最大で何ステップかかりうるか、という問いです。これらの数、つまりビジービーバー数は、どんな計算可能関数よりも速く増大します。もしそれを計算する方法があれば、停止性問題が解けてしまうからです。既知の値は、2状態、3状態、4状態でそれぞれ6、21、107ステップです。5状態では、ハイナー・マルクセン(Heiner Marxen)とユルゲン・ブントロック(Jürgen Buntrock)のチャンピオンが 47,176,870 ステップかかり、この値は2024年にオンラインの共同研究 bbchallenge によって、コンピューターで検証された証明で確定しました。6状態では、通常の記法では書き表せないほど多くのステップ動く機械が知られています。
試してみよう
チューリングマシン・シミュレーターを開いて、用意された8つのプログラムを実行したり、自分でプログラムを書いたりしてみましょう。ヘッドを1ステップずつ追ってどの規則が使われるかを確かめ、停止しないカウンターを眺め、回文を調べ、ビジービーバーを動かしてみてください。4状態のチャンピオンの107ステップは図に収まり、5状態のチャンピオンの4700万ステップも最速なら数秒で終わります。
よくある質問
チューリングマシンは実際に作られたのですか?
テープが無限なので、チューリングが記述したとおりには作られていません。しかし、このアイデアのすぐ後に本物のプログラム内蔵方式のコンピューターが登場し、チューリング自身も第二次世界大戦後にその設計に携わりました。その後、愛好家たちが木材や LEGO、さらにはライフゲームを使って動く模型を作っています。いずれもテープは有限ですが、終了する計算であればそれで十分です。
3状態のステップ数14と21の違いは何ですか?
ビジービーバーの問いは2つあります。書く 1 の最大数と、かかるステップの最大数です。3状態では、シミュレーターの機械は14ステップで最大の6個の 1 を書きますが、別の3状態の機械は最大の21ステップかかるものの、1 を5個しか残しません。2状態、4状態、5状態では、1台の機械が両方で勝っています。
チューリング完全とは強力だという意味ですか?
十分な時間とメモリがあれば計算可能なものは何でも計算できるという意味で、速さについては何も言っていません。チューリングマシンは簡単な算術にも多くのステップを必要としますし、カードゲーム、表計算ソフトの数式、Minecraft のレッドストーンのように、ほとんど偶然にチューリング完全になっているシステムもあります。
コンピューターでプログラムを実行して、停止するかどうかを確かめるだけではだめなのですか?
実行すれば、プログラムが停止する場合にはそれがわかります。しかしまだ停止していないとき、永遠に停止しないのか、単にもっと時間が必要なだけなのかはわかりません。チューリングの証明は、あらゆるプログラムに通用する、より巧妙な方法もないことを示しています。ただし、個々のプログラムの多くについては、この問いに答えることができます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
チューリングマシン・シミュレーターを開く