アルゴリズムの解決不可能性はアルゴリズムAIの障害ではありません

アルカディとボリス・ストルガツキーの素晴らしい作品「月曜日は土曜日に始まる」には、次のような対話があります。

「親愛なる人たち」と心配してフョードル・シメノビッチは言って、手書きを整理しました。 「これはベン・ベザレルの問題です。」 カリオストロは、解決策がないことを証明しました。

「彼女には解決策がないことを私たちは知っています」とフンタは言った。 「それを解決する方法を知りたい。」

「なんとなく奇妙な理由だ、クリスト...そこにない解決策を探す方法は？」 ナンセンスな何か...

「ごめんなさい、セオドア、でもあなたは非常に奇妙な推論をしている。」 解決策があるとしても、それを探しても意味がありません。 解決策のないタスクをどのように扱うかについてです。 これは非常に根本的な問題であり、残念ながら、残念ながら、アプリケーションマネージャであるあなたには利用できません。



解決できない問題を解決することは、芸術的な比phorだけではありません。 ここで議論できるのは、この問題が実践にとってそれほど重要ではないという事実だけです。 逆説的に、人工知能の分野全体は、実際には、解決不可能で不十分な問題を解決することに専念しています。 しかし、これらのタスクは何ですか？

いくつかの数学的問題の不溶性に関する最初の結論は、1931年にゲーデルによって得られました。最も有名なのは、形式的な算術の不完全性に関するゲーデルの定理の2つです。 その本質は次のとおりです。 数値の性質とそれらの算術演算を記述する一貫した公理のセットをとると、選択された公理に基づいて証明も反証もできない数についてのいくつかのステートメントがあります（そのようなステートメントは派生不可能と呼ばれます）。 さらに、これらのステートメントの一部は、完全に自然な（人間の観点から）真実のステートメントです。 これらのステートメントを「証明」するには、新しい公理を導入する必要があります。 しかし、どのような正式なシステムを採用しても、システム自体の内部で真実を確立できないシステムオブジェクトに関するステートメントは常に存在します。 人間は何らかの「神秘的な」方法で、これらのステートメントが真か偽かを判断し、望ましい結果を得るために正式なシステムを拡張できます。 それはどういう意味ですか？ 一部の思想家は、思考、特にその創造的な要素を形式化することは不可能であると結論付けています。 また、チューリングマシンも正式なシステムであるため、コンピューターでは思考を実装できないと考えています。



実際、一部のタスクには完全なアルゴリズムによる解決策がありません。 最も広く知られているのは、シャットダウンの問題です。 停止のタスクは、特定のプログラムが初期データで停止するか、場合によっては「ループ」するかを決定することです（無限に動作します）。 問題は、プログラムのシャットダウンの問題を解決できるアルゴリズムがないことが証明されていることです。 つまり、シャットダウンの問題はアルゴリズム的に解決できません。 シャットダウンの問題の重要性は、一般に信じられているように、テープの状態が回答に対応するときに停止した場合、一部のアルゴリズムが問題を解決したという事実によるものです。 停止が発生しない場合、問題が解決されなかったと見なされます。これは、ソリューションがテープに表示される時点が明確ではないためです。 シャットダウンの問題を解決するアルゴリズムも停止する必要があります。このアルゴリズムに基づいて、シャットダウンの問題が解決できないことの証明が行われます。 この証明は、嘘つきのパラドックスの類似物を使用しています。 自分自身を参照するステートメントを作成すると、パラドックスが発生します。 たとえば、次の嘘つきは「今でも常に嘘をついています」と偽っていますか？ ブレークの問題に同じトリックを使用するには？..

反対から停止する問題の不溶性の証拠の考えを考えてください。 解けるようにします。つまり、あるプログラムで供給できるアルゴリズムTが存在し、プログラムが「ループ」している場合は0を、停止する場合は1を出力します。 単純にアルゴリズムTを呼び出し、その記述T（P）を入力に渡し、アルゴリズムTが0を返す場合、アルゴリズムPが停止し、アルゴリズムTが1を返す場合、アルゴリズムPは意図的に「ループ」して無限ループを開始するプログラムPを考えます。 どのアルゴリズムTでも、プログラムPを作成するのは簡単です。これは明らかに存在します。 しかし、このプログラムを実行するとどうなりますか？ 彼女はループまたは停止しますか？ プログラムPが停止した場合、アルゴリズムTは、おそらくプログラムの停止の問題を解決し、T（P）を呼び出すときに1を呼び出す必要がありますが、プログラムPはループする必要があります。 プログラムPがループする場合、アルゴリズムT（P）は0を返しますが、プログラムPは停止する必要があります。 矛盾に遭遇しました。つまり、アルゴリズムTの存在に関する最初の仮定は誤りです。



他の多くのアルゴリズム的に不溶性の問題があります。 特に、ディオファントス方程式に関するヒルベルトの10番目の問題はアルゴリズム的に不溶であり、1970年にソビエトの数学者ユーリ・ウラジミロヴィチ・マティヤセビッチによって証明されました。 解決策があれば、それは有限（ただし無制限）のステップ数で取得できますが、解決策がなければ、どのような場合でもこれを確立することはできません。

解決策はまだ見つかっておらず、これらの問題が解決できないかどうかは不明です。 時には、驚くほど単純な処方があります。 そのような最も古い問題の1つは18世紀半ばのオイラー問題です。少なくとも4つの偶数は、2つの素数の合計として表すことができます（4 = 2 + 2、... 18 = 5 + 13、...）。 オイラーは、少なくとも7の任意の奇数を3つの素数の合計として表すことができるゴールドバッハ仮説に応じてこの問題を定式化した。 オイラー問題はまだ解決されていませんが、ゴールドバッハの仮説はそれほど前に証明されていません。 これはおそらくオイラー問題には当てはまりませんが、いくつかの数学的記述は真実である可能性がありますが、ゲーデルの定理が言うように、この公理学の枠組みでは証明不可能（還元不可能、アルゴリズム的に解決不可能）です。

アルゴリズムの機能はそれほど制限されておらず、コンピューターに基づいて作成できるのは汎用的ではない弱いAIだけですか？ これは、思考が本当に非アルゴリズム的であることを意味しますか？ これを理解するには、いくつかの点を考慮する必要があります。



最初の点は、アルゴリズム問題は通常、大規模な問題、つまり、同じタイプの無限の一連の問題を解決するために単一のアルゴリズムを見つける必要がある問題として定式化されるということです。 アルゴリズム的に解決できない問題は「非常に大規模」です。たとえば、ブレークダウン問題では、有限の時間のアルゴリズムおよびソースデータの問題を解決する必要があります。 明らかに、誰もアルゴリズムのシャットダウンの問題を解決できません。そうでなければ、「フリーズ」オペレーティングシステムや他のプログラムはありません（そして、これらは「すべてのアルゴリズム」のセットにある想像を絶する複雑なプログラムと比較してまだ比較的単純なプログラムです） "）。 人はシャットダウンの問題を解決しますが、エラーを伴います。エラーはプログラムの複雑さとともに増加します。 アルゴリズム的に不溶性の問題（質量問題など）を解決する人の能力は、非常に疑わしいものです。 個々の特定のケースの解決策を見つける彼の能力は、コンピューターの力の範囲内であるため、何も証明しません。 そしてこれがなければ、人間と比較したコンピューターの根本的な限界についての哀れみは破綻します。



プログラムTが私たちの証明に現れる状況に似た状況を想像してください。 1と言うと0を印刷し、0と言うと1を印刷するオートマトンがあるとします。そして、オートマトンが何を印刷するかという質問に答えるよう求められます。 この場合、0または1だけを言うことができます。当然、マシンはあなたが言ったことの反対を印刷し、それについては知っていますが、何もできません。 そのような「タスク」は単にあなたのock笑だとは思わないのですか？

このような実験には興味深い実用的な実装があります。事実は、多くの決定の実現は、脳内でこの解決策が生じるよりもやや遅れて（場合によっては0.5秒以上）発生することです。 最も単純な解決策（2つの選択肢、たとえば右手を上げるか左手を上げるか）は、意識する前であっても、準備の可能性として検出できます。 実際、意識の瞬間は意思決定の瞬間に対応していません。 それは行動自体まで「延期」されます-それが私たちが身体による意識的命令の実行の遅れに気付かない理由です（妨害された遅延メカニズムを持つ患者では、彼らは外部から制御されているように見えるかもしれません）。 筋肉の生体電流を記録する筋電計と、後に脳から直接情報を「読み取る」脳波計を使用した同様の実験が、1970年代から行われています。 興味深いことに、人はどの手をどの時点で上げるかを選択するよう求められ、完全な意志の自由を残します。 それにもかかわらず、EEG信号を受信するマシンは、被験者の前で被験者の決定について学習します。 人の片方の手が0を意味し、もう片方の手が1を意味し、人が選択した数字とは反対の数字を機械に印刷させます。 被験者が機械が何を印刷しているかを推測する必要がある場合、正しい選択をすることはできませんが、人の選択が頭に浮かぶ前に機械は自動的に答えを表示します。 この問題は「人為的に不溶性」です。



しかし、Tアルゴリズムはまさにそのような状況にあります。選択についての情報は、その例から、また人の例の脳からも読み取られます。 答えの正しさが選択肢自体から変わる場合、正しい答えを選ぶことはできません。 さらに、ここでは、アルゴリズムTが必ず0または1を出力し、プログラムPのみが入力として機能する必要があります。たとえば、42。アルゴリズムTが超インテリジェントで状況を完全に理解していても、実験者に考えていることすべてを説明することしかできませんでしたが、プログラムPのループについて正しい答えを与えることはできませんでした。 そして、ここでのポイントは、アルゴリズムの限られた概念ではありません。 実際、シャットダウンの問題を解決する非アルゴリズムデバイスが作成されたと仮定した場合、上記の推論は、「アルゴリズム」という用語を別の用語、例えば「非アルゴリズム情報変換デバイス」に置き換えるだけで適用できます。

実際、チューリングによるこのような仮想デバイスは1939年に検討されました。 これらはOracleマシンです。 オラクルは、未計算の関数を「計算」したり、アルゴリズム的に解決できない問題を解決したりできるエンティティとして理解されています。 チューリングは、そのようなマシンについて、それ自体に関して定式化された問題（たとえば、オラクルでマシンを停止する問題）はそれらによって解決できないことを示しました。 これは古代のパラドックスに似ています：全能の神は彼自身が持ち上げることのできない石を作ることができますか？..したがって、過剰な計算が物理的に実行可能であるとしても、彼らにとって不溶性の問題もあります。 どうやら、これらの問題を提起するまさにその形式には何か問題があります。アルゴリズムや神聖な方法で解決することはできません。



ある問題のアルゴリズム上の解決不可能性の証拠は、問題を停止問題に減らすことであることが多いことに留意する必要があります。これは、固定アルゴリズムがそれ自体より複雑でないために解決できません。 それにもかかわらず、「アルゴリズム的に解決できない」問題が存在するという事実は残っています。 唯一の質問はそれをどう解釈するかです。

2番目の重要な点は、実行されたコンピュータープログラムはアルゴリズムプロセスの形式をとっていますが、正式なアルゴリズムではないことです。 実際のコンピューターとチューリングマシンの間には重要な違いがあります-外界との相互作用です。 チューリングマシンでは、テープの内容は固定されており、マシン自体によってのみ変更されます。 新しいデータやプログラムでさえ、その動作中にコンピューターに入力される場合があります。 人はどのようにして正式なシステムを超えますか？たとえば、正式な算術では推論できないどの文が真であると見なされ、どの文が偽であるかをどのようにして知るのですか？ 答えは簡単です-経験から。 人にとって、「入力テープ」は潜在的には宇宙全体です（ここで、思考アルゴリズムは、普遍的なマシンとしての脳が実行する一部の言語で「記述」されます）。 数学の公理の選択はarbitrary意的ですが、現実の世界で何かを記述するために興味深い公理が選択されます。 ディラックは次のように書いています。「...数学者が興味深いと感じる原則は、自然によって選ばれたものだけであることが判明しました。」 しかし、実際には、数学者は経験の一般化を除いて、公理と原則をとる場所がありません。 より一般的なのは、この一般化のアルゴリズムとは何か、それがアルゴリズムであるかどうかという問題です。



コンピューターに実装された人工知能は、世界から完全に隔離されている場合にのみ制限されます。 そうすれば、それは本当に正式なシステムになり、ゲーデルの定理の結果が適用され、そこに入れたものだけが可能になります。 物理的に実装されたアルゴリズムプロセスでユニバース全体が「入力テープ」でもある場合、停止問題の定式化はそれに対して単純に不正確になります。入力テープでは、Tアルゴリズムのソフトウェア実装にもTアルゴリズム自体が含まれます。 さらに、プログラムPはアルゴリズムTの作業コピーにアクセスできず、そのコピーの別のコピーのみを呼び出すため、パラドックスは削除されます！ この場合、シャットダウン問題の解決不可能性からの結論、およびゲーデルの定理からそのようなプログラムへの結論は、単に適用されません。 これはシャットダウンの問題のアルゴリズムの解決可能性を証明するものではありませんが、コンピューターと人が同じ条件下に置かれた場合の違いを排除します。



3番目のポイントは、アルゴリズムを停止するための要件です。 もちろん、古典的なアルゴリズムが結果とともに停止アルゴリズムを要求することは非常に自然ですが、人工知能が停止し、限られた時間の後に何らかの最終結果を出すことを要求するのはばかげています。 ノンストップアルゴリズムは、従来のアルゴリズムよりも強力で、非常に便利です。 たとえば、そのような「アルゴリズム」は何らかの結果をもたらし、機能し続ける可能性があります。 多くの科学者は、ノンストップアルゴリズムのアイデアが好きではありません。答えが形成されると考えるとき疑問が残るため、そのようなアルゴリズムの特性は数学であまり研究されていません。 しかし、彼らにとって「限界の計算可能性」の概念を導入することができます。ある段階で、ノンストッププログラムのその後の作業中に変化しない回答が形成される場合、問題は解決されたとみなされます。 残念ながら、古典的なシャットダウンの問題が限界で解決できるという事実はほとんど知られていません。 したがって、潜在的な人工知能アルゴリズムのノンストップ性は悪くはありませんが、根本的に必要な特性です。 事実、ノンストップアルゴリズムの複雑さは無限に増加する可能性がありますが、（アルゴリズムまたはソースデータ内の）事前に決められた数のステップで停止する必要があるアルゴリズムの機能は実際には限られています。



したがって、アルゴリズム的に不溶性の問題の存在と、フォーマルシステムに対するゲーデルの定理によって課せられた制限は、明らかに、何らかのアルゴリズムプロセスの物理的実現として強力な人工知能を実現する可能性に対する議論の余地のない議論ではありませんが、それはノンストップでオープンなプロセスです。

思考のアルゴリズム化可能性に対する他の「議論」があります。 たとえば、アルゴリズムの結果は初期データによって完全かつ明確に決定されるが、人には「自由意志」があるとよく言われます。 ただし、決定論はアルゴリズムの重要な特性ではありません。 確率的および非決定的チューリングマシンがあり、その結果はあいまいです。 しかし、問題のアルゴリズムの解決可能性という意味で、アルゴリズムの概念を拡張しないことがわかった。 また、特定のカオスの原因は思考の実装にとって重要かもしれませんが、これはアルゴリズム性の考え方に反論するものではありません。 さらに、外部からプログラムに入力されるデータには大きな不確実性があります。

もう一つ興味深いのは、私たちにとってよく知られているアルゴリズムの機械的適用は、精神活動の現れのようには見えないということです。 「列内の」2つの数値を乗算するアルゴリズムがわからない場合、数値の各特定のペアの乗算には知的ストレスが必要になります。 しかし、アルゴリズムが判明するとすぐに、任意の2つの数値の乗算はインテリジェントなタスクになります。質量問題を解決する方法がまだ不明な場合に、新しいアルゴリズムを構築するプロセスを考えているのではないでしょうか？

シャットダウンの問題やその他の多くの問題を解決するアルゴリズムの検索は、一般的に実行不可能です。しかし、これは、特定の自然な制限の下でこれらの問題を解決するためのアルゴリズムの調査を妨げません。多くの場合、これらの制限の検索は、実際の「不溶性」問題を解決する主要な部分です。問題の正しい定式化はすでに解決策の半分であると彼らが言うのも不思議ではありません。アルゴリズム的に解決できない問題の近似解を実装する方法はまだ明確ではありませんが、少なくともゲーデルの定理はこの可能性に制限を課していません。