計算可能性理論と複雑さの紹介

公開: 2022-03-11

あなたは今まで疑問に思ったことはありますか：あなたがこの記事を読んでいるデバイスは正確には何ですか？コンピューターとは何ですか？

計算科学は、これらの最新のコンピューティングデバイスが想像されるずっと前の時代にまでさかのぼります。よくある質問がプログラミング言語、フレームワーク、ライブラリを中心に展開している業界では、コンピュータを動かす基本的な概念を当然のことと思っていました。

しかし、無限の可能性を秘めているように見えるこれらのコンピューターには、何か制限がありますか？コンピューターでは解決できない問題はありますか？

この記事では、プログラミング言語とコンピュータアーキテクチャの詳細から離れて、これらの質問に対処します。コンピューターとアルゴリズムの能力と限界を理解することで、私たちはさまざまな戦略についての考え方とより良い推論を改善することができます。

コンピューティングの抽象的な見方は、1970年代に最初に開発されたときと同じように、今日の私たちにとって価値のある、時の試練に耐えてきた結果を生み出します。

計算可能性

コンピューターとは何ですか？問題は何ですか？

学校では、次のような問題や機能のメンタルモデルを教えられることがよくあります。

関数は、出力f（x）を見つけるために入力xに適用するプロシージャです。

数学的な定義が異なることがわかります。

関数は、各ペアの最初の要素がセットX（ドメインと呼ばれる）からのものであり、各ペアの2番目の要素がセットY（コドメインまたは範囲と呼ばれる）からのものであり、ドメインは、範囲の1つの要素とペアになっています。

それはかなり一口でした。しかし、それは正確にはどういう意味ですか？

この定義は、コンピューターが機能を計算するための機械であることを示しています。

なんで？

コンピュータは任意の入力を何らかの出力に変換するからです。言い換えれば、彼らは問題を解決します。関数の2つの定義、つまり私たちがよく知っているものと正式なものは、多くの実用的な目的で一致しています。

ただし、数学的な定義により、計算不可能な関数（つまり、解決できない問題）の存在などの興味深い結論に到達することができます。

なぜなら、すべての関数をアルゴリズムとして記述できるわけではないからです。

ゲームのルール

議論を助けるために、コンピューターを、何らかの入力を受け取り、一連の操作を実行し、しばらくしてからいくつかの出力を提供するマシンとして想像してみましょう。

入力をマシンのアルファベットと呼びます。つまり、ある有限集合からの文字列のセットです。たとえば、マシンのアルファベットは2進数（0と1）の場合もあれば、ASCII文字セットの場合もあります。文字の有限シーケンスは文字列です（例：「0110」）。

さらに、マシンの出力をバイナリの受け入れ/拒否の決定として表し、マシンが（うまくいけば）計算を終了すると配信されます。この抽象化は、以前の関数の数学的定義によく適合します。

これらのパラメータを考えると、もう1つのタイプ、つまり文字列のコレクションを特徴づけることが重要です。あるマシンが受け入れる文字列のセットを気にしているのかもしれませんし、特定のセットの文字列を受け入れて他のセットを受け入れないマシンを構築しているのかもしれません。あるいは、あるマシンのすべてを受け入れるマシンを設計することさえ可能かどうかを尋ねているのかもしれません。特定のセットと他のセットはありません。

これらすべての場合において、文字列のセットは言語と呼ばれます。たとえば、偶数を表すすべてのバイナリ文字列のセット、または文字数が偶数の文字列のセットです。数字のような言語は、連結、和集合、共通部分などの演算子で操作できることがわかります。

重要な演算子の1つは、正規表現でも使用されるクリーネ閉包演算子です。これは、言語のすべての可能な力の結合と考えることができます。たとえば、言語Aが文字列のセット{'01'、' 1'}である場合、 A*の1つのメンバーは文字列'0101111'です。

可算性

すべての関数が計算可能であるとは限らないという私たちの主張を証明する前のパズルの最後のピースは、可算性の概念です。直感的に、私たちの証明は、より多くの言語があることを示します。つまり、それらを解決するための可能なプログラムよりも多くの問題があります。文字列が言語に属しているかどうか（はい/いいえ）の問題自体が問題であるため、これは機能します。

より正確には、私たちの証明は、可能なプログラムのセットは数え切れないほど無限であるのに対し、アルファベット上の言語のセットは数え切れないほど無限であると主張しています。

この時点で、あなたは次のように考えているかもしれません。今、私はそれらのうちの2つに対処する必要があります！」

まあ、それはそれほど悪くはありません。可算無限集合は、列挙できるものです。これが最初の要素、これが2番目の要素というように、最終的にセットのすべての要素に番号が割り当てられると言うことができます。たとえば、偶数のセットを考えてみましょう。 2が最初のもの、4が2番目、6が3番目というように言うことができます。そのような集合は可算無限または可算です。

ただし、実数のように、いくつかのセットでは、あなたがどれほど賢いかは関係ありません。単に列挙はありません。これらの集合は、数え切れないほど無限または数えられません。

可算多くのプログラム

まず、コンピュータプログラムのセットが可算であることを示したいと思います。私たちの目的のために、有限のアルファベット上のすべての文字列のセットが可算であることを観察することによってこれを行います。コンピュータプログラム自体が有限の文字列であるため、これは機能します。

証明は簡単で、ここでは詳細を説明しません。重要なポイントは、自然数などと同じ数のコンピュータプログラムが存在することです。

繰り返しますが：

任意のアルファベット上のすべての文字列のセット（たとえば、すべてのコンピュータープログラムのセット）は可算です。

数え切れないほど多くの言語

この結論を考えると、これらの文字列のサブセットはどうですか？別の言い方をすれば、すべての言語のセットはどうですか？このセットは数えられないことがわかりました。

アルファベット上のすべての言語のセットは数えられません。

繰り返しになりますが、ここではその証拠については説明しません。

結果

それらはすぐには明らかにならないかもしれませんが、言語の不可算性とすべてのコンピュータプログラムのセットの可算性の結果は深刻です。

なんで？

AがASCII文字のセットであると仮定します。 ASCII文字は、コンピュータプログラムを構成するために必要な文字です。たとえば、JavaScriptプログラムを表す文字列のセットは、 A *のサブセットであることがわかります（ここで、*はクリーネ閉包演算子です）。 JavaScriptの選択は任意です。このプログラムのセットは可算集合のサブセットであるため、JavaScriptプログラムのセットは可算である必要があります。

さらに、任意の言語Lについて、文字列xがLにある場合は1に評価され、そうでない場合は0に評価される関数fを定義できると考えてみましょう。そのような機能はすべて異なります。すべての言語のセットと1：1の対応があり、すべての言語のセットは数えられないため、そのようなすべての関数のセットは数えられないことがあります。

ここに重要なポイントがあります：

すべての有効なプログラムのセットは可算ですが、関数のセットはカウントできないので、プログラムを作成できない関数がいくつかあるはずです。

これらの機能や問題がどのように見えるかはまだわかりませんが、存在することはわかっています。解決策がない問題がいくつかあるので、これは謙虚な認識です。私たちはコンピューターを非常に強力で有能であると考えていますが、それでもいくつかのことは彼らの手の届かないところにあります。

ここで、問題は「これらの問題はどのように見えるか」になります。このような問題を説明し続ける前に、まず一般化された方法で計算をモデル化する必要があります。

チューリングマシン

コンピューターの最初の数学的モデルの1つは、AlanTuringによって開発されました。チューリングマシンと呼ばれるこのモデルは、計算可能性の概念を完全に捉えた非常にシンプルなデバイスです。

マシンへの入力は、入力が書き込まれたテープです。読み取り/書き込みヘッドを使用して、マシンは一連のステップを通じて入力を出力に変換します。各ステップで、テープに書き込むかどうか、何を書き込むか、およびテープを右または左に移動するかどうかが決定されます。この決定は、正確に2つのことに基づいています。

頭の下の現在の記号、および
シンボルが書き込まれると更新されるマシンの内部状態

それでおしまい。

普遍

1926年、アランチューリングはチューリングマシンを開発しただけでなく、彼の有名な論文「計算可能数について」を書いたときに、計算の性質について他の多くの主要な洞察を持っていました。彼は、コンピュータープログラム自体がコンピューターへの入力と見なすことができることに気づきました。この観点から、彼はチューリングマシンがその入力をシミュレートまたは実行できるという美しいアイデアを持っていました。

今日、これらのアイデアは当然のことと考えていますが、チューリングの時代には、このような万能マシンのアイデアは、チューリングが解決できない問題を開発することを可能にした大きな進歩でした。

チャーチチューリングテーゼ

先に進む前に、重要な点を調べてみましょう。チューリングマシンは計算モデルであることがわかっていますが、それで十分一般的ですか？この質問に答えるために、私たちはチャーチチューリングテーゼに目を向けます。これは次の声明に信憑性を与えます。

計算可能なものはすべてチューリングマシンで計算可能です。

チューリングが計算モデルとしてチューリングマシンを開発した一方で、アロンゾチャーチはラムダ計算として知られる計算モデルも開発しました。これらのモデルは強力です。どちらも計算を記述し、今日のどのコンピューターにも、さらに言えば、これまでのどのコンピューターにも匹敵する方法で計算を行うからです。これは、チューリングマシンを使用して、私たちが求めている解決できない問題を説明できることを意味します。私たちの調査結果は、過去、現在、およびそれ以降のすべての可能なコンピューターに適用されることを知っています。

認識可能性と決定可能性

解決できない問題、つまり言語認識機能と言語決定機能の概念を具体的に説明する前に、もう少し背景を説明する必要があります。

言語を認識するチューリングマシンがあれば、その言語は認識できます。
と
言語を決定するチューリングマシンがあれば、言語は決定可能です。

言語を認識するために、チューリングマシンはその言語のすべての文字列を受け入れる必要があり、その言語以外のものを受け入れてはなりません。そのような文字列を拒否またはループする場合があります。決定者になるには、チューリングマシンは、受け入れるか拒否するかのいずれかによって、常に入力を停止する必要があります。

ここでは、入力を停止するという考えが重要です。実際、決定者は認識者よりも強力であることがわかります。さらに、問題は解決可能です。言い換えれば、関数によって記述される言語を決定するチューリングマシンが存在する場合にのみ、関数は決定可能です。

決定不能性

コンピュータプログラムを書いたことがあるなら、プログラムが実行されるときにコンピュータが回転するのを見ているだけでそこに座っている感覚を知っている必要があります。プログラムに時間がかかっているだけなのか、コードに間違いがあり、無限ループが発生しているのかはわかりません。コンパイラが実行時にコードが停止またはループするかどうかを確認するためにコードをチェックしないのはなぜか疑問に思われるかもしれません。

コンパイラは、単純に実行できないため、このようなチェックはありません。コンパイラエンジニアが十分に賢くない、またはリソースが不足しているわけではありません。任意のコンピュータプログラムをチェックして、停止しているかどうかを判断することは不可能です。

これはチューリングマシンを使用して証明できます。チューリングマシンはストリングとして記述できるので、数え切れないほどの数があります。 M ₁ 、 _M2などがすべてのチューリングマシンのセットを構成するとします。次の関数を定義しましょう。

Miが<Mj>を受け入れる場合はf（ _i 、 _j ）= 1、それ以外の場合は0

ここで、<M>は「Mの文字列エンコーディング」の構文であり、この関数は、M _jを入力として受け入れ、それ以外の場合は0を出力することにより、 _Miが停止した場合に1を出力する問題を表します。 M _iは停止する必要があることに注意してください（つまり、決定者になる）。これは、決定不可能な関数（つまり、解決できない問題）を記述したいので必要です。

ここで、独自の記述を受け入れないチューリングマシンの文字列エンコーディングで構成される言語Lも定義しましょう。

L = {<M> | Mは<M>を受け入れません}

たとえば、あるマシンM1は入力<M1>に₀を出力し、別のマシン_M2は入力< _M2 >に₁を出力する場合があります。この言語が決定不能であることを証明するために、言語Lを決定するマシンであるM _Lが、入力として独自の記述< _ML >を与えられたときに何をするかを尋ねます。 2つの可能性があります：

_MLは< _ML >を受け入れます
また
_MLは< _ML >を拒否します

M _Lが独自のエンコーディングを受け入れる場合、それは< _ML >が言語Lではないことを意味します。ただし、その場合、MLはそもそもそのエンコーディングを_{受け入れる}べきではありませんでした。一方、M _Lが独自のエンコーディングを受け入れない場合、<M _L >は言語Lであるため、 _MLはその文字列エンコーディングを受け入れる必要があります。

どちらの場合も、言語Lが決定不可能であることを証明する、パラドックス、または数学的には矛盾があります。したがって、最初の解決できない問題について説明しました。

停止性問題

今説明した問題は関連性がないように見えるかもしれませんが、実際に重要な追加の解決できない問題、特に停止性問題に減らすことができます。

空の文字列で停止するチューリングマシンのエンコーディングの言語。

停止性問題は、コンパイラが以前の無限ループを検出できない理由の問題に当てはまります。プログラムが空の文字列で終了するかどうかを判断できない場合、その実行によって無限ループが発生するかどうかをどのように判断できますか？

この時点で、簡単な結論に達するために手を振ったように見えるかもしれません。しかし、実際には、チューリングマシンでは、コンピュータープログラムが停止するのか、それともループに永久に留まるのかを判断できないことに気づきました。これは実際のアプリケーションでは重要な問題であり、チューリングマシンやその他の種類のコンピューターでは解決できません。 iPhoneではこの問題を解決できません。多くのコアを備えたデスクトップでは、この問題を解決できません。クラウドはこの問題を解決できません。誰かが量子コンピューターを発明したとしても、それでも停止性問題を解決することはできません。

概要

計算可能性理論の検討では、数え上げの引数によって、単語の通常の意味では計算できない関数がどのようにあるかを見てきました。計算の意味を正確に定義し、チューリングマシンを形式化するためのペンと紙に関する彼自身の経験から、チューリングのインスピレーションにまでさかのぼります。このモデルが、現在または将来のコンピューターで可能なことをどのように計算できるかを見てきました。そして、まったく計算できないクラスの問題に気づきました。

それでも、計算可能性には欠点があります。問題を解決できるからといって、すぐに解決できるわけではありません。結局のところ、何千万年も先の私たちに太陽が新星になる前に計算が終わらないのであれば、コンピューターは何が良いのでしょうか。

計算可能な関数と言語を残して、計算の複雑さ、効率的な計算の調査、有名なPvs.NP問題について説明します。

複雑

遅いvs.速い

コンピューター科学者はさまざまなクラスの問題を認識しており、私たちが関心を持っている2つのクラスには、コンピューターが迅速または効率的に解決できるPと呼ばれる問題と、解決策を迅速に検証できるが迅速に取得できないNPと呼ばれる問題があります。

たとえば、あなたがオンラインデートサービスのアルゴリズムを開発する責任があり、誰かが「誰もがデートをすることができますか？」という質問をしたとします。答えは、全員がペアになるように互換性のある個人をペアリングすることに要約されます。この問題を解決するための効率的なアルゴリズムがあることがわかりました。この問題は集合Pにあります。

さて、ユーザーの中で最大のクリークを特定したい場合はどうでしょうか。クリークとは、互いに互換性のある個人の最大のネットワークを意味します。ユーザー数が少ない場合、この問題は迅速に解決できます。たとえば、3人のユーザーがいるクリークを簡単に識別できます。しかし、より大きなクリークを探し始めると、問題の解決はますます難しくなります。この問題は集合NPにあります。

正式な定義

Pは、多項式時間で解ける問題のセットです。つまり、計算ステップの数は、問題のサイズに関して多項式関数によって制限されます。「誰もがデートできますか？」二部マッチング問題としても知られる質問は、 Pにあります。

NPは、多項式時間で検証可能な一連の問題です。もちろん、これにはPのすべての問題が含まれます。ただし、この封じ込めが厳格かどうかはわかりません。効率的に検証できるが効率的に解決できない問題はわかっていますが、問題が本当に手に負えないものであるかどうかはわかりません。クリーク問題はそのような問題の1つです。解決策を効率的に検証できることはわかっていますが、問題を効率的に解決できるかどうかはわかりません。

最後に、 NP完全は、 NPで最も難しい問題のセットです。 NPの問題は効率的にNPCに変換できるため、これらは最も難しいと呼ばれます。その結果、誰かがNPCの問題に対する効率的な解決策を特定した場合、 NPのクラス全体がPによって吸収されます。クリーク問題はNPCにもあります。

したがって、 P対NPの問題に到達します。多くのコンピューター科学者や数学者は、 PとNPは等しくないと強く信じています。もしそうなら、その影響は深遠なものではありません。今日のデジタルインフラストラクチャの多くは、 Pにはない問題がNPにあるという事実に依存しています。そうでない場合、たとえば暗号化方式は一夜にして崩壊し、 NPCの問題に対する効率的な解決策を持っている人は、最も厳しいセキュリティプロトコルでさえも破壊することができます。

扱いやすさの微妙さ

コンピュータサイエンスの初心者にとって、マッチング問題とクリーク問題の違いは大したことではないように思われるかもしれません。実際、 Pの問題とNPの問題の違いは非常に微妙です。違いを見分けることができることは、現実の世界でアルゴリズムを設計する人にとって重要です。

最短経路問題を考えてみましょう。 2つの場所が与えられた場合、目的はそれらの間の最短経路を特定することです。 iPhoneはこれを数ミリ秒で計算します。これは計算上扱いやすい問題です。

一方、巡回セールスマン問題を考えてみましょう。この問題の目的は、可能な限り最短の距離を移動しながら、出発地で終わる可能性のある目的地のサブセットを訪問することです。この問題は最短経路問題に似ていますが、NP完全です。また、サプライチェーンロジスティクスが10億ドル規模の産業である理由についても説明します。

私たちは実際にはもっと微妙になることができます。最短経路（P）を求める代わりに、サイクルなしで最長経路を求めることができます。最長パスの問題もNP完全であることがわかります。

この微妙な違いの例は他にもたくさんあります。たとえば、2部グラフと一般的なグラフでの頂点被覆の識別や、句ごとに2つと3つのリテラルを使用したブール式の満足度などです。重要なのは、問題がPにあるのかNPにあるのかがすぐにはわからないということです。これが、実行時間分析が重要なスキルである理由です。設計しなければならないアルゴリズムがPの問題に対するものである場合、効率的な解決策があることがわかります。一方、問題がNPにある場合、アルゴリズムは一般に問題を解決するのに時間がかかりすぎるため、解決策を追求することに反対する強いケースがあります。

概要

この複雑さの検討では、問題のクラスPとNPを定義しました。 Pは非公式にコンピューターで効率的に解決できる問題を表し、NPは効率的に検証できる問題を表します。

PがNPと等しくないことを証明できる人は誰もいません。これらの2つのクラスの問題が同等であるかどうかは、P vs. NP問題として知られており、すべての数学ではないにしても、今日の理論計算機科学で最も重要な未解決の問題です。実際、2000年に、クレイ数学研究所はP vs. NP問題を数学の7つの最も重要な未解決の質問の1つとして挙げ、この問題の解決策を決定する証拠として100万ドルの報奨金を提供しました。

結論

この記事では、「コンピューターとは何か」などの大きな質問に答えながら、計算可能性と複雑さの領域を掘り下げました。詳細は圧倒される可能性がありますが、覚えておく価値のある重要なポイントがいくつかあります。

停止性問題のように、単純に計算できないことがいくつかあります。
NPCの問題のように、効率的に計算できないことがいくつかあります。

詳細よりも重要なのは、計算と計算問題について考える方法です。私たちの職業生活の中で、そして私たちの日常の中でさえ、私たちはこれまでに見たことのない問題に遭遇するかもしれません、そして私たちは最善の行動方針を決定するために試行錯誤された真のツールとテクニックを使うことができます。

Toptal Engineeringブログでさらに読む：

インタプリタを最初から書く方法