Loading article…
計算可能性理論において、チャーチ＝チューリングのテーゼ[ a ]は、計算可能な関数の性質に関するテーゼである。このテーゼは、自然数上の関数が有効な方法で計算できるのは、チューリングマシンで計算できる場合に限ると述べている。このテーゼは、アメリカの数学者アロンゾ・チャーチとイギリスの数学者アラン・チューリングにちなんで名付けられた。計算可能な関数の厳密な定義がなされる以前は、数学者は紙と鉛筆による方法で計算可能な関数を説明するために、しばしば「実質的に計算可能」という非公式な用語を使用していた。1930年代には、計算可能性の概念を形式化するために、いくつかの独立した試みが行われた。
チャーチ[ 13 ] 、クリーネ[ 14 ]、チューリング[ 15 ] [ 17 ]は、これらの形式的に定義された3つの計算可能関数のクラスが一致することを証明しました。関数がλ-計算可能であるのは、それがチューリング計算可能である場合のみであり、かつ、それが一般再帰的である場合のみである、ということです。このことから、数学者やコンピュータ科学者は、計算可能性の概念はこれら3つの等価なプロセスによって正確に特徴付けられると考えるようになりました。その後、計算可能性を特徴付けるための他の形式的な試みによって、この考えがさらに強固になりました（下記参照）。
一方、チャーチ＝チューリングのテーゼは、上記の3つの形式的に定義された計算可能関数のクラスが、実質的に計算可能な関数という非形式的な概念と一致すると述べている。このテーゼはほぼ普遍的に受け入れられているものの、実質的な計算可能性という概念は非形式的に定義されているに過ぎないため、形式的に証明することはできない。
創始以来、このテーゼには様々なバリエーションが生じており、例えば、コンピュータが我々の宇宙で物理的に実現できるもの（物理的チャーチ＝チューリングのテーゼ）や、効率的に計算できるもの（チャーチ＝チューリングのテーゼ（計算複雑性理論））に関する記述などが挙げられる。これらのバリエーションはチャーチやチューリングによるものではなく、後の計算複雑性理論やデジタル物理学の研究から生まれたものである。このテーゼは心の哲学にも影響を与える（下記参照）。
JB Rosser ( 1939 )は、「有効な計算可能性」の概念について次のように述べている。「明らかに、CC と RC [つまり、真理を決定する有効な方法はないという主張の Church と Rosser の証明] の存在は、「有効」の正確な定義を前提としている。「有効な方法」は、ここでは、各ステップが正確に決定されており、有限のステップで答えを出すことが確実な方法という、かなり特別な意味で使用されている。」[ 18 ]したがって、副詞形容詞「有効な」は、「1a: 決定的、決定的、または望ましい効果を生み出す」および「結果を生み出すことができる」という意味で使用されている。[ 19 ] [ 20 ]
以下では、「実効的に計算可能」とは「直感的に『実効的』な手段によって生成される」という意味であり、「実効的に計算可能」とは「チューリングマシンまたは同等の機械装置によって生成される」という意味である。チャーチの指導の下、1938年にチューリングが提出した博士論文『順序数に基づく論理体系』の脚注に記されたチューリングの「定義」は、実質的に同じである。
†「計算可能な関数」という表現は、機械で計算可能な関数を意味し、「実質的に計算可能」とは、これらの定義のいずれかに特に関連付けることなく、直感的な概念を指すものとする。[ 21 ]
このテーゼは次のように述べることができる。「すべての有効な計算可能な関数は計算可能な関数である。 」 [ 22 ]チャーチはまた、「チューリングマシンとして表現できない限り、いかなる計算手順もアルゴリズムとはみなされない」と述べた。[ 23 ]
チューリングはそれを次のように述べた。
「関数の値が何らかの純粋に機械的なプロセスによって求められる場合、その関数は実質的に計算可能である」と述べられている。これを文字通りに解釈し、純粋に機械的なプロセスとは機械によって実行できるプロセスであると理解してもよい。この展開は、計算可能性†と実質的な計算可能性の同一視 につながる。[ †は上記の脚注である。] [ 21 ]
1930年代の論理学者にとって重要な問題の一つは、デイヴィッド・ヒルベルトとヴィルヘルム・アッカーマンの決定問題[ 24 ]であり、数学的真理と数学的虚偽を区別する機械的な手順が存在するかどうかを問うものでした。この探求には、「アルゴリズム」または「有効計算可能性」の概念を、少なくとも探求を開始するのに十分な程度に明確に定義する必要がありました[ 25 ] 。しかし、アロンゾ・チャーチの試みは最初から、今日まで続く議論から始まりました[ 26 ] 。「有効計算可能性」の概念は、（i）公理系における「公理または複数の公理」なのか、（ii）単に2つ以上の命題を「識別」する定義なのか、（iii）自然現象の観察によって検証される経験的仮説なのか、（iv）単なる議論のための提案（つまり「テーゼ」）なのか？
この問題の研究過程で、チャーチと彼の学生スティーブン・クリーネはλ定義可能関数の概念を導入し、数論で頻繁に遭遇するいくつかの大きなクラスの関数がλ定義可能であることを証明することができた。[ 27 ]議論は、チャーチがゲーデルに「実効的に計算可能な」関数をλ定義可能関数として定義すべきだと提案したことから始まった。しかし、ゲーデルは納得せず、その提案を「全く不十分」と呼んだ。[ 28 ]むしろ、ゲーデルはチャーチとの書簡（1934年頃～1935年）の中で、 「実効的計算可能性」の概念を公理化することを提案した。実際、1935年にクリーネに宛てた手紙の中で、チャーチは次のように報告している。
当時のゲーデルの唯一の考えは、未定義の概念としての有効計算可能性の観点から、この概念の一般的に受け入れられている性質を具体化する一連の公理を述べ、それに基づいて何かを行うことが可能かもしれないということだった。[ 29 ]
しかし、ゲーデルはそれ以上の指針を示さなかった。最終的に、彼はヘルブラントの提案によって修正された自身の再帰を示唆することになるが、それはゲーデルが1934年にニュージャージー州プリンストンで行った講義で詳しく説明したものであった（クリーネとロッサーがそのノートを書き起こした）。しかし、彼は「発見的方法以外では」この2つのアイデアを満足に同一視することはできないと考えていた。[ 30 ]
次に、有効計算可能性の 2 つの概念の等価性を特定し証明する必要があった。 λ 計算と「一般」再帰を備えた Kleene は、Church と J. Barkley Rosser の助けを借りて、2 つの計算が等価であることを示す証明 (1933 年、1935 年) を作成した。 Church はその後、Herbrand–Gödel 再帰の使用を含めるように方法を修正し、Entscheidungsproblem は解決不可能であることを証明した (1936 年)。つまり、整形式式がベータ正規形を持つかどうかを決定できるアルゴリズムは存在しない。[ 31 ]
何年も後、デービスへの手紙（1965年頃）の中で、ゲーデルは「これらの[1934年の]講義の時点では、自分の再帰の概念がすべての可能な再帰を包含しているとは全く確信していなかった」と述べている。[ 32 ] 1963年から1964年までに、ゲーデルはヘルブランド＝ゲーデル再帰とλ計算を否定し、「アルゴリズム」または「機械的手順」または「形式体系」の定義としてチューリングマシンを支持するようになる。[ 33 ]
自然法則につながる仮説？：1936年後半、アラン・チューリングの論文（決定問題が解決不可能であることを証明したもの）は口頭で発表されたが、まだ印刷物としては出版されていなかった。[ 34 ]一方、エミール・ポストの1936年の論文は既に発表されており、チューリングの研究とは独立していることが確認されていた。[ 35 ]ポストは、チャーチが実効計算可能性をλ計算と再帰と「同一視」したことに強く反対し、次のように述べている。
実際、チャーチらが既に行った研究は、この同一性を作業仮説の段階をはるかに超えて進めている。しかし、この同一性を定義の下に隠してしまうと 、その継続的な検証の必要性が見えなくなってしまう。[ 36 ]
むしろ彼は、「有効計算可能性」という概念を、定義や公理ではなく帰納的推論によって「自然法則」に導く可能性のある単なる「作業仮説」とみなした。 [ 37 ]この考えはチャーチによって「厳しく」批判された。[ 38 ]
したがって、ポストは1936年の論文で、1934年から1935年にかけてゲーデルがチャーチに提案した、この命題は公理または公理の集合として表現できるかもしれないという提案も否定していた。[ 29 ]
チューリングは別の定義を追加し、ロッサーは3つすべてを同一視した。 チューリングの1936年から1937年の論文「計算可能な数について、決定問題への応用」[ 34 ]が発表された。その中で彼は、aマシン（現在はチューリングマシン抽象計算モデルとして知られている）の導入により、「実効計算可能性」の別の概念を述べた。1936年から1937年の論文の付録として追加された証明スケッチで、チューリングはλ計算とチューリングマシンによって定義される関数のクラスが一致することを示した。[ 39 ]チャーチはチューリングの分析がいかに説得力があるかをすぐに認識した。チューリングの論文のレビューで、彼はチューリングの概念が「通常の（明示的に定義されていない）意味での実効性との同一視をすぐに明らかにした」ことを明確にした。[ 40 ]
数年後（1939年）、チューリングは、彼以前のチャーチやクリーネと同様に、機械的計算エージェントの形式的定義が正しいと提唱した。 [ 41 ]このように、1939年までに、チャーチ（1934年）とチューリング（1939年）はそれぞれ、彼らの「形式体系」が「有効計算可能性」の定義であるべきだと提唱したが、 [ 42 ]どちらもその主張をテーゼとして提示しなかった。
ロッサー（1939）は、定義としての概念を3つ正式に特定した。
これら3つの定義はすべて同等なので、どれを使っても構いません。[ 43 ]
クリーネはテーゼIを提唱する：これにより、「テーゼ」の明示的な表現はクリーネに委ねられた。1943年、クリーネは「テーゼI」を提唱した：[ 44 ]
この発見的事実［一般的な再帰関数は実質的に計算可能である］ から、チャーチは次のテーゼを提唱した。チューリングによる計算機の説明にも、同じテーゼが暗黙のうちに含まれている。
テーゼI.すべての実効的に計算可能な関数（実効的に決定可能な述語）は一般的に再帰的である[クリーネの強調]実質的に計算可能（実質的に決定可能）という用語の厳密な数学的定義がこれまで欠けていたため、本論文を その定義として用いることができる 。
… この命題は仮説の性質を帯びている――これはポストとチャーチが強調した点である。命題とその逆を定義とみなすならば、この仮説は、その定義から展開された数学理論の適用に関する仮説である。そして、我々が示唆したように、この仮説を受け入れるには非常に説得力のある根拠が存在する。
チャーチ＝チューリングのテーゼ：スティーブン・クリーネは、『メタ数学入門』の中で、自身の再帰的実現可能性の理論を用いて、ついに「チャーチのテーゼ」と「チューリングのテーゼ」という正式な名称を定めた。これは、それまでチャーチ＝クリーネのラムダ定義可能性の用語を用いていた研究を、ゲーデル＝クリーネの再帰性（部分再帰関数）の用語に切り替えたためである。この移行において、クリーネはゲーデルの一般再帰関数を修正し、EJ・ブラウワーの直観主義における問題の解けなさを証明できるようにした。彼の論理学の大学院教科書では、「チャーチのテーゼ」が紹介され、基本的な数学的結果が実現不可能であることが示された。次に、クリーネは「チューリングのテーゼ」を提示し、エミール・ポストの研究に基づくチューリングマシンの簡略化された導出を用いて、結果が計算不可能であることを示した。両方の命題は「定理XXX」を用いることで同等であることが証明される。
テーゼ I.すべての実効的に計算可能な関数（実効的に決定可能な述語）は一般的に再帰的である。[ 45 ]
定理 XXX: 次の部分関数のクラスは同外延的である、つまり同じメンバーを持つ: (a) 部分再帰関数、(b) 計算可能な関数 ... [ 46 ]
チューリングのテーゼ：チューリングのテーゼ、すなわち、自然に計算可能と見なされるすべての関数は、彼の定義の下で、つまり彼の機械のいずれかによって計算可能であるというテーゼは、定理 XXX によりチャーチのテーゼと同等である。[ 46 ]
クリーネは最後に、ウィリアム・ブーンからの批判を受けて、アラン・チューリングの論文「相殺を伴う半群における語の問題」の概念を明確にするのに役立つ章で、「チャーチ＝チューリングのテーゼ」という用語を初めて使用した。[ 47 ]
「実効計算可能性」の概念をよりよく理解しようとする試みから、ロビン・ガンディ（チューリングの教え子であり友人）は1980年に機械計算（チューリングマシンによって実行される人間による計算とは対照的に）を分析した。ガンディはセルオートマトン（コンウェイのライフゲームを含む）、並列処理、結晶オートマトンに対する好奇心と分析から、 あらゆる機械が満たさなければならないと主張される4つの「原理（または制約）」を提案した[ 48 ]。彼の最も重要な4番目の原理である「因果律」は、「効果と信号の伝播速度が有限であること」に基づいている。「現代物理学は遠隔での瞬間的な作用の可能性を否定している」。[ 49 ]これらの原理といくつかの追加制約（(1a) 部品の線形寸法の下限、(1b) 伝播速度の上限（光速）、(2) 機械の離散的な進行、(3) 決定論的な動作）から、彼は「原理 I～IV を満たす装置で計算できるものは計算可能である」という定理を導き出した。[ 50 ]
1990年代後半、ウィルフリード・ジークはチューリングとガンディの「実効計算可能性」の概念を分析し、「非形式的な概念を明確化し、その一般的な特徴を公理的に定式化し、公理的枠組みを調査する」ことを意図した。[ 51 ]ジークは1997年と2002年の著作で、コンピュータ（「機械的に進む人間の計算エージェント」）の振る舞いに関する一連の制約を提示している。これらの制約は以下のように要約される。
このテーゼは、単なる普通の数学的定義と見なすことができる。この主題に関するゲーデルのコメントは、この見解を示唆している。例えば、「機械的計算可能性の正しい定義は、チューリングによって疑いの余地なく確立された」[ 55 ] 。このテーゼを単なる定義と見なすという主張は、ロバート・I・ソア[11]によって明確に述べられており、チューリングの計算可能性の定義は、連続関数のイプシロンデルタ定義よりも正しい可能性が低いわけではないとも主張されている。
再帰、λ計算、チューリングマシン以外にも、有効計算可能性/計算可能性を記述するための形式が提案されている。クリーネ（1952）は、クルト・ゲーデル（1936）の「システムS 1で計算可能な」関数と、エミール・ポスト（1943、1946）の「正準[正規]システム」をリストに追加している。[ 56 ] 1950年代には、ハオ・ワンとマーティン・デイビスが1テープのチューリングマシンモデルを大幅に簡略化した（ポスト・チューリングマシンを参照）。マービン・ミンスキーはモデルを2つ以上のテープに拡張し、テープを「アップダウンカウンタ」に大幅に簡略化した。メルザックとランベックはこれをさらに発展させ、現在カウンタマシンモデルとして知られるものになった。 1960年代後半から1970年代初頭にかけて、研究者たちはカウンタマシンモデルをレジスタマシンへと拡張しました。レジスタマシンは、現代のコンピュータの概念に非常に近いものです。他のモデルには、組み合わせ論理やマルコフアルゴリズムなどがあります。グレヴィッチは、コルモゴロフとウスペンスキーのポインタマシンモデル（1953年、1958年）も付け加えています。「…彼らは、計算可能な関数の概念を拡張する方法はないと、自分たちに納得させたかっただけなのです。」[ 57 ]
これらの貢献はすべて、モデルがチューリングマシンと計算的に等価であることを証明することを含みます。このようなモデルはチューリング完全であると言われます。これらの「実効計算可能性/計算可能性」の概念を形式化しようとするさまざまな試みはすべて同等の結果をもたらしたため、現在ではチャーチ＝チューリングのテーゼが正しいと一般的に考えられています。実際、ゲーデル（1936）はこれよりも強いことを提案しました。彼は「S 1で計算可能」という概念には「絶対的」な何かがあると指摘しました。
また、システム S iのいずれか、あるいは超限型のシステムにおいて計算可能な関数は、 S 1においても既に計算可能であることが示される。したがって、「計算可能」という概念はある明確な意味で「絶対的」であるのに対し、他のほとんどすべての馴染みのあるメタ数学的概念（例えば、証明可能、定義可能など）は、本質的にそれらが定義されているシステムに依存している ... [ 58 ]
計算可能性理論の証明では、厳密な形式的証明で必要となる（しばしば非常に長い）詳細を避けつつ、関数の計算可能性を確立するために、非公式な方法でチャーチ・チューリングのテーゼがしばしば用いられる。[ 59 ]関数がチューリングマシンで計算可能であることを確立するには、通常、その関数を効果的に計算する方法を非公式な英語で説明し、その後「チャーチ・チューリングのテーゼにより」その関数がチューリング計算可能である（あるいは、部分再帰的である）と結論づければ十分であると考えられている。
ディルク・ファン・ダーレンは、チャーチ＝チューリングのテーゼのこの非公式な使用法を説明するために、次の例を挙げている。[ 60 ]
例: 各無限再帰列挙可能(RE) 集合は無限再帰集合を含みます。
証明：A を無限正規表現とする。A の要素を n 0、 n 1、 n 2、 n 3、 ...と列挙する。
このリストから増加する部分リストを抽出します。m 0 = n 0とします。有限回のステップの後、 n k > m 0となるn kを見つけ、m 1 = n kとします。この手順を繰り返して m 2 > m 1などを見つけます。これにより、A の部分集合 B={m 0 , m 1 , m 2 ,...} の有効なリストが得られ、m i < m i+1という性質を持ちます。
主張：Bは決定可能である。なぜなら、kがBに含まれるかどうかをテストするには、あるiについてk = m iであるかどうかをチェックする必要があるからである。m iの列は増加列であるため、リストの要素を最大でk+1個生成し、それらをkと比較する必要がある。それらのどれもがkと等しくない場合、kはBに含まれない。このテストは有効であるため、Bは決定可能であり、チャーチのテーゼにより再帰的である。
上記の例を完全に厳密にするには、チューリングマシンやλ関数を慎重に構築するか、再帰公理を慎重に適用するか、あるいはせいぜい計算可能性理論の様々な定理を巧みに適用する必要があるだろう。しかし、計算可能性理論家は、チューリング計算可能性が効果的に計算できるものを正しく捉えていると信じており、集合Bを決定するための効果的な手順が英語で明確に示されているため、この集合が実際に再帰的であることの証明としてこれを受け入れる。
チャーチ＝チューリングのテーゼの成功は、そのテーゼの様々なバリエーションの提案を促した。例えば、物理的チャーチ＝チューリングのテーゼは、「物理的に計算可能な関数はすべてチューリング計算可能である」と述べている。[ 61 ]： 101
チャーチ＝チューリングのテーゼは、ある計算モデルが別の計算モデルをどれだけ効率的にシミュレートできるかについては何も述べていない。例えば、（マルチテープ）ユニバーサルチューリングマシンは、任意のチューリングマシンをシミュレートする際に対数的な速度低下しか受けないことが証明されている。[ 62 ]
チャーチ・チューリングのテーゼの変形は、任意の「妥当な」計算モデルを効率的にシミュレートできるかどうかを扱っています。これは実現可能性テーゼと呼ばれ、[ 63 ] （古典的な）複雑性理論チャーチ・チューリングのテーゼ、または拡張チャーチ・チューリングのテーゼとしても知られていますが、チャーチやチューリングによるものではなく、複雑性理論の発展の中で徐々に実現されたものです。それは次のように述べています。[ 64 ]「確率的チューリングマシンは、現実的な計算モデルを効率的にシミュレートできる。」ここで「効率的に」という言葉は、多項式時間での還元までを意味します。このテーゼは、もともとイーサン・バーンスタインとウメシュ・ヴァジラニ（1997）によって計算複雑性理論チャーチ・チューリングのテーゼと呼ばれていました。複雑性理論チャーチ・チューリングのテーゼは、すべての「妥当な」計算モデルが、多項式時間で計算できる同じクラスの問題を生み出すと仮定しています。確率的多項式時間 ( BPP ) が決定論的多項式時間 ( P ) に等しいという予想を仮定すると、複雑性理論のチャーチ・チューリングのテーゼでは「確率的」という言葉は省略可能である。同様のテーゼである不変性テーゼは、Cees F. Slot と Peter van Emde Boas によって提唱された。それは、「『妥当な』マシンは、時間的に多項式で制限されたオーバーヘッドと空間的に定数倍のオーバーヘッド内で互いにシミュレートできる」と述べている。[ 65 ]このテーゼは元々STOC '84 の論文で発表されたもので、チューリングマシン上でのランダムアクセスマシンのシミュレーションにおいて、多項式時間オーバーヘッドと定数空間オーバーヘッドを同時に達成できることを示した最初の論文であった。[ 66 ]
BQP がBPPの厳密な上位集合であることが示されれば、複雑性理論のチャーチ・チューリングのテーゼは無効になる。言い換えれば、効率的な確率的アルゴリズムが存在しないタスクを実行する効率的な量子アルゴリズムが存在することになる。しかし、量子コンピュータは常にチューリングマシンでシミュレートできるため、これは元のチャーチ・チューリングのテーゼを無効にするものではないが、効率上の理由から古典的な複雑性理論のチャーチ・チューリングのテーゼを無効にすることになる。したがって、量子複雑性理論のチャーチ・チューリングのテーゼは次のように述べている。[ 64 ]「量子チューリングマシンは、あらゆる現実的な計算モデルを効率的にシミュレートできる。」
ユージン・エーベルバッハとピーター・ウェグナーは、チャーチ＝チューリングのテーゼが時として広範に解釈されすぎていると主張し、「チューリングマシンはアルゴリズムの振る舞いを表現しているが、アルゴリズムが計算可能なものを正確に捉えているというより広範な主張は無効である」と述べている。[ 67 ]彼らは、このテーゼで捉えられていない計算形式が今日でも重要であり、それをスーパーチューリング計算と呼んでいると主張している。
哲学者たちは、チャーチ＝チューリングのテーゼが心の哲学に影響を与えるものとして解釈してきた。[ 68 ] [ 69 ] [ 70 ] B.ジャック・コープランドは、チューリングマシンによるシミュレーションを長期的には回避する実際の決定論的な物理プロセスが存在するかどうかは未解決の経験的問題であると述べている。さらに、そのようなプロセスが人間の脳の働きに関与しているかどうかも未解決の経験的問題であると述べている。[ 71 ]また、チャーチ＝チューリングのテーゼと物理学の関係、およびハイパーコンピューティングの可能性を網羅する重要な未解決問題もいくつかある。物理学に適用した場合、このテーゼにはいくつかの意味がある可能性がある。
これら3つのカテゴリーに該当しない、あるいはその中間に位置する技術的な可能性は他にも数多く存在するが、これらは概念の適用範囲を示すための例として挙げられる。
物理的コンピュータと生物学的コンピュータの両方に関するこの論文の哲学的側面は、オディフレディの1989年の再帰理論に関する教科書でも議論されている。[ 74 ]： 101-123
計算不可能な関数を形式的に定義することは可能である。そのような関数のよく知られた例として、ビジービーバー関数がある。この関数は入力nを受け取り、入力なしで実行した場合に、 n個の状態を持つチューリングマシンが停止するまでに出力できる最大の記号数を返す。ビジービーバー関数の上限を求めることは、停止問題を解くことと同等であり、停止問題はチューリングマシンでは解けないことが知られている。ビジービーバー関数はチューリングマシンでは計算できないため、チャーチ＝チューリングのテーゼによれば、この関数はいかなる方法でも効果的に計算することはできない。
いくつかの計算モデルでは、（チャーチ＝チューリングの）計算不可能な関数を計算することが可能です。これらはハイパーコンピュータとして知られています。
マーク・バーギンは、帰納的チューリングマシンなどの超再帰的アルゴリズムがチャーチ＝チューリングのテーゼを否定すると主張している。[ 75 ]彼の議論は、通常のアルゴリズムの定義よりも広い定義に基づいているため、一部の帰納的チューリングマシンから得られる非計算可能な関数は計算可能と呼ばれる。このチャーチ＝チューリングのテーゼの解釈は、上で述べた計算可能性理論で一般的に受け入れられている解釈とは異なる。超再帰的アルゴリズムがチャーチ＝チューリングのテーゼの意味でのアルゴリズムであるという議論は、計算可能性研究コミュニティ内で広く受け入れられていない。
{{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)