Loading article…
計算可能関数は、計算可能性理論における基本的な研究対象です。計算可能関数は、アルゴリズムの直観的概念を形式化した類似物であり、関数が計算可能であるのは、関数の仕事を行うことができるアルゴリズムが存在する場合、つまり、関数ドメインの入力が与えられた場合に、対応する出力を返すことができる場合です。計算可能関数は、チューリングマシンやレジスタマシンなどの具体的な計算モデルを参照せずに計算可能性を議論するために使用されます。ただし、定義はいずれも特定の計算モデルを参照する必要がありますが、有効な定義はすべて同じクラスの関数を生成します。計算可能関数の集合を生み出す特定の計算可能性モデルは、チューリング計算可能関数と一般再帰関数です。
チャーチ＝チューリングのテーゼによれば、計算可能関数とは、無制限の時間と記憶容量が与えられた場合に機械的（つまり自動）計算装置を使用して計算できる関数とまったく同じです。より正確には、これまでに考えられたすべての計算モデルは計算可能関数のみを計算でき、すべての計算可能関数は、チューリングマシン、レジスタマシン、ラムダ計算、一般再帰関数など、一見非常に異なる複数の計算モデルのいずれかによって計算できます。
計算可能関数の正確な定義がされる前、数学者はしばしば「有効に計算可能」という非公式な用語を使用していました。この用語はそれ以来、計算可能関数と同一視されるようになりました。これらの関数の有効に計算可能であることは、それらが効率的に計算可能であること（つまり、妥当な時間内に計算可能であること）を意味するものではありません。実際、有効に計算可能な関数の中には、それらを計算するアルゴリズムが非常に非効率的であることが示されています。つまり、アルゴリズムの実行時間は入力の長さに応じて指数関数的に（または超指数関数的に）増加するということです。実行可能計算可能性と計算複雑性の分野では、効率的に計算できる関数を研究します。
ブルームの公理は、計算可能関数の集合に関する抽象的な計算複雑性理論を定義するために使用できます。計算複雑性理論では、計算可能関数の複雑性を決定する問題は関数問題として知られています。
意味
関数の計算可能性は非公式な概念です。これを説明する 1 つの方法は、関数の値が有効な手順によって取得できる場合、関数は計算可能であると言うことです。より厳密に言えば、関数が計算可能であるのは、任意のk組の自然数が与えられた場合に値を生成する有効 な手順がある場合のみです。[1]この定義に従って、この記事の残りの部分では、計算可能関数は有限個の自然数を引数として受け取り、単一の自然数である値を生成するものと仮定します。
この非公式な記述に対応するものとして、複数の正式な数学的定義が存在する。計算可能関数のクラスは、以下を含む 多くの同等の計算モデルで定義することができる。
これらのモデルは関数、その入力、その出力に対して異なる表現を使用するが、2つのモデル間では翻訳が存在するため、すべてのモデルは本質的に同じクラスの関数を記述し、形式的な計算可能性は自然であり、狭すぎないという意見が生まれている。[2]これらの関数は、非公式な用語である「計算可能」と対比して「再帰的」と呼ばれることがある。[3]この区別は、1934年のクリーネとゲーデルの議論に由来する。[4] p.6
たとえば、計算可能関数をμ 再帰関数として形式化することができます。これは、自然数の有限の組を受け取り、単一の自然数を返す部分関数です(上記と同じ)。これらは、定数関数、後続関数、および射影関数を含む部分関数の最小のクラスであり、合成、原始再帰、およびμ 演算子に対して閉じています。
同様に、計算可能関数は、チューリングマシンやレジスタマシンなどの理想的な計算エージェントによって計算できる関数として形式化できます。正式に言えば、部分関数は 、次の特性を持つコンピュータプログラムが存在する場合にのみ計算できます。
- が定義されている場合、プログラムはコンピュータのメモリに格納されている値で入力を終了します。
- が未定義の場合、プログラムは入力で終了することはありません。
計算可能関数の特性
計算可能な関数の基本的な特性は、関数の計算方法を示す有限の手順 (アルゴリズム) が存在する必要があることです。上記の計算モデルは、手順とは何か、どのように使用されるかについて異なる解釈を提供しますが、これらの解釈には多くの共通する特性があります。これらのモデルが計算可能な関数の同等のクラスを提供するという事実は、各モデルが他のモデルの手順を読み取り、模倣できるという事実に由来しています。これは、コンパイラが1 つのコンピュータ言語の命令を読み取り、別の言語の命令を発行できるのと同じです。
エンダートン[1977]は計算可能関数を計算する手順について次のような特徴を与えている。同様の特徴付けはチューリング[1936]、ロジャース[1967]などによっても与えられている。
- 「手順には、長さが有限の正確な指示 (つまりプログラム) が必要です。」したがって、計算可能なすべての関数には、関数の計算方法を完全に記述した有限のプログラムが必要です。指示に従うだけで関数を計算できます。推測や特別な洞察は必要ありません。
- 「手順にfのドメイン内のk組xが与えられた場合、有限数の離散ステップの後に手順は終了し、f ( x ) を生成する必要があります。」直感的に、手順はステップごとに進行し、計算の各ステップで何を行うかをカバーする特定のルールがあります。関数の値が返されるまでに実行できるステップは有限個だけです。
- 「手順にfのドメインにないk組xが与えられた場合、手順は停止することなく永遠に続く可能性があります。または、ある時点で停止する (つまり、その命令の 1 つが実行できない) 可能性がありますが、xでfの値を生成するふりをしてはなりません。」したがって、 f ( x )の値が見つかった場合、それは正しい値でなければなりません。手順は結果を生成する場合にのみ正しいと定義されているため、コンピューティング エージェントが正しい結果と誤った結果を区別する必要はありません。
エンダートンは、計算可能な関数の手順に関するこれら 3 つの要件について、いくつかの説明を列挙しています。
- この手順は理論的には、任意の大きさの引数に対して機能するはずです。引数が、たとえば地球上の原子の数よりも小さいとは想定されていません。
- 出力を生成するには、手順は有限数のステップの後に停止する必要がありますが、停止するまでに任意の数のステップが必要になる場合があります。時間制限は想定されていません。
- 計算が正常に完了するまで、プロシージャは限られた量のストレージ スペースしか使用しませんが、使用されるスペースの量に制限はありません。プロシージャが要求するたびに、追加のストレージ スペースをプロシージャに提供できるものと想定されています。
要約すると、この見解に基づくと、関数は次の場合に計算可能です。
- ドメインからの入力が与えられ、おそらく無制限の記憶領域に依存して、有限個の正確で明確な命令によって形成された手順 (プログラム、アルゴリズム) に従って、対応する出力を生成することができます。
- 有限数のステップでそのような出力（停止）を返す。
- ドメイン外の入力が与えられた場合、停止しないか、スタックしてしまいます。
計算複雑性の研究分野では、計算を正常に実行するために許容される時間や空間の制限が規定されています。
計算可能な集合と関係
自然数の集合Aが計算可能(同義語:再帰的、決定可能) であるとは、任意の自然数nに対して、nがAに含まれる場合はf ( n ) = 1となり、nがAに含まれない場合はf ( n ) = 0となるような計算可能な全関数fが存在する場合を言います。
自然数の集合は、各数nに対して、nがその集合に含まれる場合にのみf ( n )が定義されるような計算可能な関数fが存在する場合、計算可能列挙可能(同義語:再帰的に列挙可能、半決定可能) と呼ばれます。したがって、集合が計算可能列挙可能であるのは、それが何らかの計算可能な関数の定義域である場合のみです。列挙可能という単語が使用されるのは、自然数の 空でない部分集合Bに対して以下が同値であるためです。
- B は計算可能な関数のドメインです。
- B は全計算可能関数の値域です。B が無限大の場合、関数は単射であると想定できます。
集合B が関数fの値域である場合、リストf (0)、f (1)、...にはBのすべての要素が含まれるため、関数はBの列挙として見ることができます。
自然数上の各有限関係は、対応する自然数の有限列の集合と同一視できるため、計算可能関係と計算可能列挙関係の概念は、集合の類似物から定義できます。
形式言語
コンピュータサイエンスの計算可能性理論では、形式言語を考慮するのが一般的です。アルファベットは任意の集合です。アルファベット上の単語は、アルファベットの記号の有限のシーケンスです。同じ記号が複数回使用される場合があります。たとえば、バイナリ文字列は、アルファベット{0, 1}上の単語とまったく同じです。言語は、固定されたアルファベット上のすべての単語のコレクションのサブセットです。たとえば、正確に 3 つの 1 を含むすべてのバイナリ文字列のコレクションは、バイナリアルファベット上の言語です。
形式言語の重要な特性は、与えられた単語がその言語に含まれるかどうかを判断するのに必要な難易度です。計算可能な関数が言語内の任意の単語を入力として受け取ることができるように、何らかのコーディング システムを開発する必要があります。これは通常、日常的な作業と見なされます。アルファベット上の各単語 w に対して、単語が言語に含まれる場合はf ( w ) = 1、単語が言語に含まれない場合はf ( w ) = 0となるような計算可能な関数fが存在する場合、その言語は計算可能 (同義語: 再帰的、決定可能) であると呼ばれます。したがって、任意の単語が言語に含まれるかどうかを正しく判断できる手順が存在する場合にのみ、言語は計算可能です。
言語が計算可能列挙可能（同義語：再帰的列挙可能、半決定可能）であるとは、計算可能関数fが存在し、その関数f ( w )が定義されるのは、その言語に単語wが含まれる場合のみである。列挙可能という用語は、計算可能列挙可能な自然数の集合と同じ語源を持つ。
例
次の関数は計算可能です。
- 有限の定義域を持つ各関数。たとえば、任意の有限の自然数列。
- 各定数関数 f : N k → N、f ( n 1 ,... n k ) := n。
- 加算 f : N 2 → N、f ( n 1、n 2 ) := n 1 + n 2
- 2つの数の最大公約数
- 2つの数値のベズー係数
- 数の最小の素因数
fとgが計算可能であれば、 f + g、f * gも計算可能であり、fが単項の場合 、 max( f , g )、 min( f , g )、arg max { y ≤ f ( x )}などの組み合わせも計算可能です。
次の例は、どのアルゴリズムが計算するかは不明ですが、関数は計算可能である可能性があることを示しています。
- πの 10 進展開で少なくとも n連続する 5のシーケンスがある場合にf ( n ) = 1 となり、そうでない場合はf ( n ) = 0となるような関数f は計算可能です。(関数fは、計算可能な定数 1 関数であるか、またはn < kの場合はf ( n ) = 1 、n ≥ kの場合はf ( n ) = 0となるkが存在します。このような関数はすべて計算可能です。π の 10 進展開で任意の長さの 5 の連続があるかどうかは不明であるため、これらの関数のどれがfであるかはわかりません。それでも、関数f が計算可能であることはわかっています。)
- 計算不可能な自然数列 (ビジービーバー関数Σなど)の各有限セグメントは計算可能です。たとえば、各自然数nに対して、有限列 Σ(0)、Σ(1)、Σ(2)、...、Σ( n ) を計算するアルゴリズムが存在します。これは、すべてのnに対してΣ( n )を計算するアルゴリズムが存在しないという事実とは対照的です。したがって、「Print 0, 1, 4, 6, 13」は、Σ(0)、Σ(1)、Σ(2)、Σ(3)、Σ(4) を計算する簡単なアルゴリズムです。同様に、nの任意の値に対して、Σ(0)、Σ(1)、Σ(2)、...、Σ( n ) を計算する簡単なアルゴリズムが存在します(誰にも知られたり作成されたりしないかもしれませんが) 。
チャーチ＝チューリングのテーゼ
チャーチ＝チューリングのテーゼは、上記の 3 つの特性を持つ手順から計算可能な関数はすべて計算可能関数であると述べています。これらの 3 つの特性は正式には述べられていないため、チャーチ＝チューリングのテーゼは証明できません。次の事実は、テーゼの証拠としてよく取り上げられます。
- 計算の同等のモデルは数多く知られており、それらはすべて計算可能な関数の同じ定義（場合によってはより弱いバージョン）を提供します。
- 一般的に効果的に計算可能であると考えられる、より強力な計算モデルは提案されていません。
チャーチ＝チューリングのテーゼは、計算手順を具体的に記述することで、特定の関数が計算可能であることを証明する際に使用されることがあります。これが認められているのは、何らかの計算モデルで関数の正式な手順を記述するという面倒な作業によって、このテーゼのこのような使用をすべて排除できると考えられているためです。
証明可能性
関数（または同様に集合）が与えられた場合、それが計算可能かどうかだけでなく、特定の証明システム（通常は1 階のペアノ算術）で証明できるかどうかも気になるかもしれません。計算可能であることが証明できる関数は、証明可能完全と呼ばれます。
証明可能完全関数の集合は再帰的に列挙可能である。つまり、計算可能性を証明する対応する証明をすべて列挙することで、証明可能完全関数をすべて列挙することができる。これは、証明システムの証明をすべて列挙し、無関係なものを無視することで実行できる。
再帰的に定義された関数との関係
再帰的定義によって定義された関数では、各値は、同じ関数または他の関数の以前に定義された他の値の固定された一次式によって定義されます。これらの値は単なる定数である可能性があります。これらのサブセットは、原始再帰関数です。別の例として、再帰的に定義されているが原始再帰ではないアッカーマン関数があります。 [5]
このタイプの定義が循環性や無限後退を回避するには、定義内の同じ関数への再帰呼び出しが、関数のドメイン上の何らかの整半順序でより小さい引数に対して行われることが必要である。たとえば、アッカーマン関数 の場合、 の定義がを参照するときは常に、自然数のペアの辞書式順序に関して となる。この場合、および原始再帰関数の場合、整順序は明らかであるが、一部の「参照」関係は整順序であることを証明するのが簡単ではない。整順序で再帰的に定義された関数はすべて計算可能である。つまり、各値は関数への再帰呼び出しのツリーを展開することによって計算でき、この展開は有限回の呼び出しの後で終了する必要がある。そうでない場合、ケーニッヒの補題により呼び出しの無限降順シーケンスが生じ、整順序の仮定に違反するからである。
証明可能な全関数ではない全関数
健全な証明システムでは、証明可能な全関数はすべて確かに全関数ですが、その逆は真ではありません。十分に強力で健全なすべての第 1 階証明システム (ペアノ算術を含む) では、その証明システムでは全関数であると証明できない全関数の存在を (別の証明システムで) 証明できます。
計算可能な全関数が、それらを生成するチューリング マシンによって列挙される場合、証明システムが健全であれば、前述の証明可能全関数の列挙を使用して、上記で使用したのと同様の対角化の議論によって上記のステートメントを示すことができます。関連する証明を列挙するチューリング マシンを使用し、すべての入力nに対して、n 番目の証明に従って計算するチューリング マシンを呼び出してf n ( n ) (ここでf nはこの列挙によるn番目の関数) を呼び出します。このようなチューリング マシンは、証明システムが健全であれば停止することが保証されています。
計算不可能な関数と解けない問題
すべての計算可能な関数には、その計算方法に関する明示的で明確な指示を与える有限の手順があります。さらに、この手順は計算モデルで使用される有限のアルファベットでエンコードされる必要があるため、計算可能な関数は可算な数しかありません。たとえば、関数はビットの文字列 (アルファベットΣ = {0, 1 }) を使用してエンコードされる場合があります。
実数は非可算なので、ほとんどの実数は計算できません。計算可能数を参照してください。自然数に対する有限関数の集合は非可算なので、ほとんどは計算できません。そのような関数の具体的な例としては、ビジービーバー、コルモゴロフ複雑度、またはチャイティン定数などの計算不可能な数の桁を出力する関数などがあります。
同様に、自然数のほとんどの部分集合は計算不可能である。そのような集合が最初に構築されたのは停止問題である。デイヴィッド・ヒルベルトが提唱した停止問題では、どの数学的命題（自然数としてコード化されている）が真であるかを決定する効果的な手順があるかどうかを問うた。チューリングとチャーチは1930年代に独立して、この自然数の集合は計算不可能であることを示した。チャーチ＝チューリングのテーゼによれば、これらの計算を実行できる効果的な手順（アルゴリズム付き）は存在しない。
計算可能性の拡張
相対的な計算可能性
関数の計算可能性の概念は、任意の自然数集合Aに相対化できます。関数fは、 Aを神託としてアクセスできるように変更された計算可能関数の定義を満たす場合、Aで計算可能（つまりA計算可能、またはAに対して計算可能）であると定義されます。計算可能関数の概念と同様に、相対的な計算可能性には、さまざまな計算モデルで同等の定義を与えることができます。これは通常、計算モデルに、与えられた整数がAのメンバーであるかどうかを尋ねる追加のプリミティブ操作を追加することで実現されます。また、 g をそのグラフと同一視することで、fがgで計算可能であることについても語ることができます。
高等再帰理論
超算術理論は、空集合のチューリングジャンプの計算可能な順序数の反復から計算できる集合を研究します。これは、2 階算術言語の普遍式と存在式の両方で定義される集合、および超計算のいくつかのモデルに相当します。任意の集合を E 再帰関数の引数として使用できる E 再帰理論など、さらに一般的な再帰理論も研究されています。
ハイパーコンピューティング
チャーチ＝チューリングのテーゼでは、計算可能な関数にはアルゴリズムを持つすべての関数が含まれると述べられていますが、アルゴリズムが備えていなければならない要件を緩和する、より広範な関数のクラスを検討することも可能です。ハイパーコンピューティングの分野では、通常のチューリング計算を超える計算モデルを研究しています。
参照
参考文献
- ^ エンダートン、ハーバート (2002)。論理学への数学的入門(第 2 版)。米国: エルゼビア。p. 209。ISBN 0-12-238452-0。
- ^ エンダートン、ハーバート (2002)。論理学への数学的入門(第 2 版)。米国: エルゼビア。p. 208,262。ISBN 0-12-238452-0。
- ^ CJ Ash、J. Knight、「計算可能構造と超算術階層」（論理学と数学の基礎研究、2000年）、p. 4
- ^ R. Soare、「計算可能性と再帰」（1995年）。2022年11月9日にアクセス。
- ^ ペーター、ロザ(1935)。 「Konstruktion nichtrekursiver Funktionen」。数学アンナレン。111：42～60。土井：10.1007/BF01472200。S2CID 121107217。