| 現在の状態 | 読む | 書く | 移動 | 次の状態 |
|---|
チューリングマシン・シミュレーター
チューリングマシンは考えうる限り最も単純なコンピューターです。ヘッドが無限に続くテープの記号を1つ読み、記号を書き、1セル左か右に動いて状態を変える、これを短い規則表に従って繰り返します。アラン・チューリングが1936年に考案したもので、お使いのコンピューターがすることはすべて、原理的にはこの方法で行えます。自分で規則を書くか例を読み込んで「実行」を押し、テープが1ステップずつ変わっていく様子を見てみましょう。その下には全履歴を示す図が表示されます。 プログラムを選ぶか自分で書き、入力を入れて「実行」を押します。「ステップ」を押すと規則を1つずつたどれ、「戻る」で1ステップ取り消せます。プログラムの各行が1つの規則で、状態、読む記号、書く記号、移動(L、R、または移動なしの N)、次の状態を並べます。例:A 0 -> 1 R B。空白のセルには _ を使います。機械は最初の規則の状態で、入力の最初の記号の上から始まり、H、accept、reject のいずれかに達するか、当てはまる規則がなくなると停止します。図は各ステップ後のテープを上から下へ示します。
使い方
- プログラム例を選ぶか、A 0 -> 1 R B のような規則を1行に1つずつ書き、入力を入れます。
- 「実行」を押すとヘッドの動きが見られ、「ステップ」を押すと規則を1つずつたどれます。「戻る」で1ステップ取り消せます。
- 状態、ステップ数、テープ上の記号はタイルで、テープの履歴は図で確認します。
機械の仕組み
機械は常にいくつかある状態のどれか1つにあり、ヘッドはテープのセルの1つの上にあります。その状態とヘッドの下の記号に対する規則が、3つのことを決めます。セルにどの記号を書くか、左右どちらに動くか、それとも動かないか、そして次にどの状態へ移るかです。機械はこれだけです。H、accept、reject のような停止状態に達するか、当てはまる規則がなくなると停止します。2進数に1を足すプログラムなら、このような規則が9つあれば十分です。
ビジービーバー
空白のテープから始めた n 状態の機械のうち、停止するまでに最も多くの 1 を書くのはどれでしょうか。ティボール・ラドー(Tibor Radó)が1962年にこの問いを立てました。そのチャンピオンはビジービーバーと呼ばれ、コンピューターが計算できるどんな関数よりも速く増大します。2状態では6ステップで 1 を4個、3状態では 1 を6個、4状態では107ステップで 1 を13個書きます。1989年に見つかった5状態のチャンピオンは 47,176,870 ステップで 1 を4,098個書きます。そして2024年、オンラインの共同研究が、コンピューターで検証された数学によって、停止する5状態の機械でこれより長く動くものはほかにないことを証明しました。
よくある質問
規則はどう書けばよいですか?
1行に1つの規則で、現在の状態、読む記号、書く記号、移動(L、R、N)、次の状態を書きます。例:A 0 -> 1 R B。矢印とコンマは省略できます。空白のセルには _ を、コメントには # を使います。機械は最初の規則の状態から始まります。次の状態が H または halt なら停止し、accept と reject なら判定結果を出して停止します。
チューリングマシンは本当に何でも計算できるのですか?
テープと時間が十分にあれば、どんなコンピューターが計算できることでも計算できます。これがチャーチ=チューリングのテーゼです。チューリングマシンにはメモリの上限がないので、その意味では実際のどのコンピューターよりも強力ですが、はるかに遅いです。できないのは、あらゆる問いに答えることです。チューリングは、あらゆるプログラムと入力について、それが停止するかどうかを判定できる機械は存在しないことを証明しました。
カウンターが止まらないのはなぜですか?
その規則が決して停止状態に至らないからです。テープの右端にある2進数に1を足しては戻ることを繰り返すので、数は永遠に大きくなり続けます。チューリングの停止性問題によれば、あらゆる機械について停止するかどうかを判定できる一般的な方法はありません。この単純なカウンターなら見ればわかりますが、わずか6状態の機械の中にも、まだ誰にも答えがわからないものがあります。
5状態のビジービーバーがここで4700万ステップも動けるのはなぜですか?
テープは両方向に伸びるコンパクトな配列として保存され、最速の設定では画面を更新する合間に数十万ステップを実行するので、最新のブラウザなら全体の実行は数秒で終わります。図に記録するのは最初の400ステップだけです。4700万行の絵はどんな画面にも収まらないからです。
何かがサーバーに送信されますか?
いいえ。プログラムはブラウザ内で動き、プログラムと入力はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ