チューリングの原理を再考し、矛盾による証明の力を感じてください。

アルゴリズムは至る所に普及しており、正確な数学用語で表現できるすべての問題には、対応するアルゴリズムがあるようです。しかし、そうではありません。実際には、一見単純に見える問題の中には、アルゴリズムでは決して解決できないものもあります。コンピュータ科学者の先駆者であるアラン チューリングは、これをほぼ 1 世紀前の論文で証明しました。この問題を解決するために、彼は現代のコンピューターサイエンスを開始する計算数学モデルを提案しました。

チューリングは、直観に反する戦略を使用して、この画期的な結果を実証しました。彼は、それを解決しようとするすべての試みに抵抗する問題を定義しました。 「例えば、私があなたに何をしているのかと尋ねたら、あなたの答えが何であれ、私は『私がやろうとしていることはあなたが言ったこととは違う』と言うだろう」とマサチューセッツ工科大学（MIT）の大学院生ラーフル・イランゴ氏は語った。理論的なコンピューターサイエンス。 書き直された内容: チューリングは、直観に反する戦略でこの画期的な結果を実証しました。彼は、それを解決しようとするすべての試みに抵抗する問題を定義しました。 「たとえば、私があなたに何をしているのかと尋ねたら、あなたの答えが何であれ、私は『私がやろうとしていることはあなたが言ったこととは違う』と言うだろう」とマサチューセッツ工科大学（MIT）の大学院生ラーフル・イランゴ氏は語った。理論的コンピューターサイエンス

#チューリングの戦略は、「対角証明」と呼ばれる長年の数学的手法に基づいています。以下は、彼の証明の背後にあるロジックの簡単な説明です。

文字列

対角線の証明は、文字列に関する問題を解決するための巧妙なトリックから来ています。ビットは 0 または 1 です。問題の説明は次のとおりです。文字列のリストが与えられ、リスト内のすべての文字列が同じ長さである場合、リストにない新しい文字列をどのように生成できますか?

書き直された内容: 最も簡単な戦略の 1 つは、考えられるすべての文字列を順番に検討することです。 5 つの文字列があり、それぞれに 5 ビットがあるとします。まず、リストに 00000 が存在するかどうかを繰り返し確認します。存在しない場合は問題は解決されており、存在する場合は 00001 に進み、プロセスを繰り返します。この方法はシンプルですが、長い文字列から生じる長いリストの場合は遅くなります。

Diagonal は、存在しない文字列を段階的に構築するための実行可能な代替手段であることがわかります。リストの最初の文字列の最初のビットから始めて、それを反転すると、これが新しい文字列の最初のビットになります。次に、2 番目の文字列の 2 番目のビットを反転して、それを新しい文字列の 2 番目のビットとして使用し、リストの最後に到達するまでこれを繰り返します。ビット演算を逆にすることで、新しい文字列が元のリスト内のすべての文字列と少なくとも 1 位置異なっていることが保証されます。 (文字列のリスト内で対角線も形成するため、対角証明と呼ばれます。)

#対角証明では、リスト内の各項目を順番にチェックするだけです。 . 文字列内の 1 ビットなので、通常は他のメソッドよりもはるかに高速ですが、その真の威力は無限に長い文字列の問題をいかにうまく処理できるかにあります。

MIT の理論コンピューター科学者であるライアン ウィリアムズは、「文字列とリストは無限になる可能性がありますが、対角化手法は依然として効果的です。」

ジョージ カンター エルは、これを最初に利用しました。権力の権威であり、集合論という数学分野の創始者でした。 1873 年、彼は対角線を使用して、一部の無限値が他の値よりも大きいことを示しました。 60 年後、チューリングは、あるクラスの数学的問題が存在することを証明するために、このバージョンの対角証明を計算理論に適用しました。どのようなアルゴリズムでも解決することは不可能であるとチューリングは理論を提案しました。このタイプの問題には、明確に定義された入力と出力がありますが、入力を出力に変換するプロセスが定義されていません。チューリングは主に意思決定の問題に焦点を当て、この漠然とした課題をより具体的にしようと努めました。決定問題では、入力は 0 と 1 で構成される任意の文字列にすることができ、出力は 0 または 1 にすることができます

数値が素数 (1 とそれ自身でのみ割り切れる) かどうかの決定は決定です。問題は、数値を表す入力文字列が与えられた場合、その数値が素数であれば正しい出力は 1 であり、素数でない場合は 0 であるということです。別の例は、コンピューター プログラムの構文エラーをチェックすることです。入力文字列は、さまざまなプログラムのコードを表します。すべてのプログラムは、コンピューター上で保存および実行される方法であるため、この方法で表すことができます。ルールは、コードに構文エラーが含まれている場合は 1 を出力し、そうでない場合は 1 を出力します。 0を出力します。

アルゴリズムがすべての可能な入力に対して正しい出力を生成する場合にのみ、そのアルゴリズムは問題を解決したと言えます。一度でも失敗した場合、そのアルゴリズムは問題を解決するための一般的なアルゴリズムではありません。通常、解決したい問題を指定し、それを解決するためのアルゴリズムを見つけようとします。チューリングは、解決不可能な問題を探すときに、この論理をひっくり返しました。彼は、考えられるすべてのアルゴリズムの無限のリストを想像し、対角化を使用して、リスト上のすべてのアルゴリズムに対抗するパズルを構築しました。

20 個の質問からなる新しい質問を想像してください。回答者は、特定の概念から始めるのではなく、質問ごとに順番に不満の例を考え出します。ゲームが終了すると、解答者は、質問の反対の内容から完全に構成される命題を説明しました。

チューリングの対角証明プロセスでは、無限に長いアルゴリズムのリスト内の各アルゴリズムを実行します。思考: 「このアルゴリズムは問題を解決できるか?」計算不可能であることを証明したい問題は?」という、ゲームのコンテストのようなものです。ウィリアムズ氏は、「この方法は、元の問題を『無限問題』に変換します。」

ゲームに勝つために、チューリングは、各アルゴリズムによって与えられる答えが次の数になる質問を設計する必要があります。これは、最初のアルゴリズムで間違った答えを出力した特定の入力、2 番目のアルゴリズムを失敗させた別の入力などを見つけることを意味します。彼は、これらの特別な入力が、クルト・ゲーデルが少し前に「この命題は証明できない」のような自己言及的主張が数学の基礎に問題を引き起こす可能性があることを示したときに使用した方法と同様の方法を使用していることを発見しました。

ここで重要なのは、すべてのアルゴリズム (またはプログラム) は 0 と 1 の文字列として表現できるということです。これは、エラー チェッカーの例と同様に、アルゴリズムが別のアルゴリズムのエンコードを入力として受け取ることができることを意味します。原則として、アルゴリズムは独自のエンコーディングを入力として受け取ることもできます。

このようにして、チューリングの証明で述べた問題と同じように、計算不可能な問題を定義できます。「アルゴリズムのコードを表す入力文字列が与えられたとき、アルゴリズム自体のコードが入力として与えられたとき、アルゴリズムが 0 を出力する場合は 1 を出力し、そうでない場合は 0 を出力します。」 この問題を解決しようとするすべてのアルゴリズムは、少なくとも 1 つの入力、つまり独自のコードに対応する入力で誤った出力を生成します。これは、この異常な問題はどのアルゴリズムでも解決できないことを意味します

証明できないことは矛盾による証明です

コンピューター科学者による対角証明の使用はここで終わりではありません。 仕上げる。 1965 年、ジュリス ハートマニスとリチャード スターンズはチューリングの議論を応用して、すべての計算可能な問題が等しいわけではなく、本質的に他の問題よりも難しい問題があることを示しました。この結果は、計算問題の難しさの研究である計算複雑性理論の分野を開始しました。

複雑性理論の発展により、チューリングの対角証明の限界が明らかになりました。 1975 年、Baker、Gill、Solovy は、複雑性理論の多くの未解決問題が対角化だけでは解決できないことを示しました。その中で最も重要なのは有名な P/NP 問題です。これは、解の正しさが多項式時間で検証できるかどうか、また多項式時間で解けるかどうかに関する単純な問題です。

対角線の証明 限界これらは、それを非常に強力なものにする高度な抽象化の直接の結果です。チューリングの証明は、実際に発生する可能性のある計算不可能な問題にはまったく対処していません。代わりに、問題は抽象的な傾向があります。他の対角線も同様に現実世界から遠く離れていることが判明するため、現実世界の問題を解決することはできません。

ウィリアムズは、「対角証明は、グローブ ボックスで実験を行うのと同じように、問題自体には直接触れません。」

対角証明の減少傾向は、P を解くことが困難であることを示しています。 /NP 問題は長い道のりになるでしょう。限界があるにもかかわらず、対角証明は依然として複雑理論家の武器の重要なツールの 1 つです。 2011 年、ウィリアムズはこれを他のさまざまな手法と組み合わせて、制限された計算モデルではいくつかの信じられないほど難しい問題を解決できないことを実証しました。その結果、研究者を 25 年間悩ませてきた問題が解決されました。これは P/NP 問題の解決にはほど遠いものの、それでも大きな進歩を示しています。

何かが不可能であることを証明したい場合は、否定の力を過小評価しないでください。

元のリンク:

書き直す必要があります。内容は: https://www.quantamagazine.org/alan-turing-and-the-power-of-negative- Thinking-20230905/

以上がチューリングの原理を再考し、矛盾による証明の力を感じてください。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。