ビジービーバーゲームの例の比類のない機能

コンピューターは人間の生活のほとんどの領域に侵入し、進化を続けています。 オートパイロット、銀行、機械翻訳、医学、金融市場、宇宙飛行-これらはすべて、1つの簡単なアイデアのおかげで可能です。

この記事では、コンピューターの能力の限界を超えて、コンピューターにできないことを検討することを提案します。 そしてその理由。 30代のアランチューリングは、コンピューターでは不可能なタスクを特定しました。

チューリングマシン

非常に正確に言うと、コンピューターサイエンス[1]の基礎を築いたまさにチューリングの出版物は、特にチューリングマシンが通過できない境界の存在を強調する計算可能な機能に関するものでした。

チューリングマシン（MT）は、アルゴリズムの概念に密接に関連する抽象的なコンピューティングマシンです[10]。 これは最も簡単なコンピューターです。

また、物理デバイスで計算できる関数はすべて、チューリングマシンで計算できることを思い出してください[2]。 これは、抽象チューリングマシンに関するすべての結論が、あらゆるアーキテクチャのあらゆるコンピューターに完全に適用可能であるという事実につながります。

比類のない機能と停止問題

停止の問題[3]は次のように定式化できます。プログラムがその説明と入力データに従って停止するかどうかを決定できる一般的なアルゴリズムはありません。

つまり 停止検出機能は計算できません。 証拠はウィキペディアで見つけることができます。

実際には、このように見えます。コンピュータ自体は、次のプログラムが命令の無限のストリームでハングするかどうかを正確に判断することはできません。 しかし、人間が書いたプログラムはどれほど不完全なのでしょう。

この問題を解決するための1つのよく知られた試みは、Microsoft Terminator [4]という名前でMicrosoftの腸で起こりました。 マイクロソフトは、ハードウェアの正確性をチェックする自動システムを構築することにより、ハードウェアのドライバーの数を減らしたいと考えていました。 彼らは、プログラムの数学モデルの正確性を証明するツールを構築しようとしました。 プラスの結果については知りませんが、ドライバーの安定性を部分的に高めることができたと思います。

忙しいビーバーゲーム

この問題は、1962年にハンガリーの数学者Tiber Radoによって、「計算不可能な関数について」という記事で特定されました[5]。 ビーバーとの類似性を使用して、彼はチューリングマシンについて説明しましたが、名前はそのままです。 この記事でさえ、当時知られている最大数が言及されました。

チューリングマシン（MT）N状態を制限する場合、有限数のマシンを作成できます。

N状態の数が増えると、可能なチューリングマシンの数は指数関数的よりも速く増加します：（4（n + 1））^ 2n。

残りのMTには、停止するものと停止しないものの2つのタイプがあります。

ラドーは2つの定式化で1つの質問をしました。

• N状態のMTが完了する前に完了できる操作の最大数はいくつですか。 これはビジービーバー番号と呼ばれ、BB（n）またはS（n）として示されます。
  
  
• MTは、完了前に空のテープにNで印刷できるユニットの最大数です。 Σ（n）として指定されます。
  
  

明らかに、この数は存在します。 そして、それを数えると、MTがこのステップ数で完了したかどうかを確認できます。 そうでない場合、最大しきい値を超えているため、永久に機能することは明らかです。

ビジービーバーゲームは、可能な限り長く実行されて終了するN状態のチューリングマシン用のプログラムを見つけることを提供します。

入力として、チューリングマシンのテープはゼロで埋められます。

最大数のユニットでプログラムを埋め、HALT状態になることで終了するプログラムを作成する必要があります。

これは、2つの状態を持つチューリングマシンのルールがどのように見えるかです（N = 2）。 同じ例は、N = 2のビジービーバーソリューションです。

プログラムは次のように実行されます。

• テープ全体が入力としてゼロで埋められます。
• 初期状態はAです。
• 現在のビットを読み取ります-1の場合はコードA1を実行し、それ以外の場合はA0を実行します。
• 指示1RBは、夏1に書き込み、右に進み、状態Bに進むことを意味します。
• プログラムは、HALT（H）状態に移行するまで継続します。

図1. N = 2での段階的なMT操作の視覚化 最初の列はステップ番号です。 2番目の列は、MTの状態が進行するにつれてどのように変化するかを示しています。 3番目の列はテープステータスで、そこにユニットが表示される順序を確認できます。 4番目は、テープに沿ったポインターの軌跡です。

このようなグラフN = 5を表示するには、少なくとも47,176,870ステップが必要です。

N = 6で、これまでに見つかった最大ビーバー数はS（6）= 7.4×10 ^ 36534です。

N = 7の場合、予備推定値はS（7）>Σ（7）> 10 ^ 10 ^ 10 ^ 10 ^ 18705352 [6]のみです。

今日、人々はS（6）を見つけて、それが最大であるという証拠を提供できるという意見があります。 S（7）は絶対にアクセスできません[8]。

テープには、{0,1}の代わりに3,4,5,6文字を書き込むことができます。 この場合、数値は増加するだけです。

この問題を解決するには？

ソリューションへの一般的なアプローチは、すべての可能なチューリングマシンを次のクラスに分割するように見えます。

• ツリー正規化 ：これらのマシンは、他のMTと同等であることが証明されているか、その動作が明らかであるため、検索スペースから除外されます[8]
• Candidate-halter ：滞在が保証されている車は、Busy Beaver Game Championの候補です。
• Non-candidate-halter ：停止しますが、特定の要件を満たしません。
• Non-halter ：それぞれに特定のノンストップ動作を示す多数の小さなクラス。
• ホールドアウト ：残っているのは、これらの車が明確に停止しないことだけです。 このクラスが空の場合、Busy Beaverタスクは解決済みと見なすことができます。

ツリーの正規化を使用すると、MTの数を大幅に削減できます。

• ツリーの正規化方法の例は、最初のステップが残っているMTの半分を削除することです。 右側に移動し始める同様のミラーマシンがあるため[8]。

スーパーチューリングコンピューティング

BB（n）を計算するためのマシンを構築できる場合、それはすでにオーバーチューリングマシンです。

スーパーチューリング計算は、チューリングマシンでは実行できない計算です[9]。 しかし、物理的なスーパーチューリングコンピューターを構築することは可能ですか？[7]

強力な人工知能を作成するための重要な質問は、人の心がチューリング計算のみを使用するかどうかです。

おわりに

なぜ解決できない問題を解決しようとするのですか？ 数学の境界線のケースが元の理論の完全性を明らかにしているからかもしれません。

ビジービーバーゲームは、計算可能性理論、停止問題、および複雑性理論と密接に関連しています。

このタスクはまた、私を不思議に思いました-チューリングマシンは、無限より少し小さい間、正確に何を計算できますか？

私のブログ

参照資料

[1]計算可能な数について

[2]チャーチチューリングテーゼ

[3]停止問題

[4]マイクロソフトターミネーター

[5]計算不可能な関数について

[6] Sの境界（7）

[7]ハイパーコンピューティング：誇大広告か計算か？

[8]単純なマシンの複雑な動作。 ロナ・マシリン

[9]スーパーチューリングコンピューティング

[10]チューリング機械

[11] Peteris KruminsによるPythonおよびC ++ソース