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

計算可能性理論において、チャーチ＝チューリングのテーゼ（計算可能性テーゼ、^[1]チューリング ＝チャーチのテーゼ、^[2]チャーチ＝チューリング予想、チャーチのテーゼ、チャーチの予想、チューリングのテーゼとも呼ばれる）は、計算可能関数の性質に関するテーゼである。これは、自然数上の関数が効果的な方法で計算できるのは、チューリングマシンで計算できる場合のみであると述べている。このテーゼは、アメリカの数学者アロンゾ・チャーチとイギリスの数学者アラン・チューリングにちなんで名付けられた。計算可能関数の正確な定義がされる前は、数学者は紙と鉛筆による方法で計算可能な関数を説明するために、非公式の用語「効果的に計算可能」を使用することが多かった。1930年代には、計算可能性の概念を形式化する試みがいくつか行われた。

1933 年、クルト・ゲーデルはジャック・エルブランとともに、一般再帰関数のクラスの定義を形式化しました。これは、合成、再帰、最小化に対して閉じており、ゼロ、後続、すべての射影を含む、任意の数の引数を持つ関数の最小のクラスです。
1936 年、アロンゾチャーチはλ 計算と呼ばれる関数を定義する手法を考案しました。 λ 計算では、チャーチ数と呼ばれる自然数の符号化を定義しました。自然数上の関数は、対応するチャーチ数上の関数が λ 計算の項で表せる場合、λ 計算可能と呼ばれます。
また、1936年、チャーチの研究を知る前に、^[6] アラン・チューリングは、テープ上の記号を操作することで入力から計算を実行できる、現在チューリングマシンと呼ばれる機械の理論モデルを作成しました。自然数を記号のシーケンスとして適切にエンコードすると、あるチューリングマシンがエンコードされた自然数に対して対応する関数を計算する場合、自然数上の関数はチューリング計算可能と呼ばれます。

チャーチ^[7]、クリーネ[ ^8]、チューリング^[9]^[11]は、計算可能関数のこれら3つの形式的に定義されたクラスが一致することを証明しました。関数がλ計算可能であるのは、チューリング計算可能である場合のみであり、一般再帰的である場合のみである。これにより、数学者とコンピュータ科学者は、計算可能性の概念はこれら3つの同等のプロセスによって正確に特徴付けられると信じるようになりました。その後、計算可能性を特徴付ける他の形式的な試みにより、この信念が強化されました（以下を参照）。

一方、チャーチ＝チューリングのテーゼは、上記の 3 つの形式的に定義された計算可能関数のクラスは、有効に計算可能な関数の非形式的な概念と一致すると述べています。このテーゼはほぼ普遍的に受け入れられていますが、有効に計算可能な概念は非形式的にしか定義されていないため、正式に証明することはできません。

当初のテーゼは、その発端以来、私たちの宇宙でコンピューターによって物理的に実現できるもの (物理的チャーチ＝チューリングのテーゼ) や、効率的に計算できるもの (チャーチ＝チューリングのテーゼ (複雑性理論)) に関する声明など、さまざまなバリエーションを生み出してきました。これらのバリエーションはチャーチやチューリングによるものではなく、複雑性理論やデジタル物理学におけるその後の研究から生まれたものです。このテーゼは、心の哲学にも影響を与えています(以下を参照)。

チャーチとチューリングの言葉による声明

JB ロッサー (1939) は、「効果的な計算可能性」という概念について次のように述べている。「明らかに、CC と RC (チャーチとロッサーの証明) の存在は、『効果的』の正確な定義を前提としている。ここでの『効果的な方法』は、各ステップが正確に事前に決定されており、有限数のステップで確実に答えが得られる方法という、かなり特殊な意味で使用されている」。^[12]したがって、副詞形容詞「効果的」は、「1a: 決定的、決定的、または望ましい効果を生み出す」および「結果を生み出すことができる」という意味で使用されている。^[13]^[14]

以下では、「効果的に計算可能」という語は「直感的に「効果的な」手段によって生成される」という意味であり、「効果的に計算可能」という語は「チューリングマシンまたは同等の機械装置によって生成される」という意味です。チャーチが指導した 1938 年の博士論文「順序数に基づく論理システム」の脚注に記載されているチューリングの「定義」は、実質的に同じです。

^†「計算可能な関数」という表現は、機械で計算可能な関数を意味するために使用し、「効果的に計算可能」は、これらの定義のいずれかに特に特定することなく、直感的なアイデアを指すものとする。^[15]

この命題は次のように述べられる。「すべての効果的に計算可能な関数は計算可能な関数である」。^[16] チャーチはまた、「チューリングマシンとして表現できない限り、計算手順はアルゴリズムとはみなされない」と述べた。^[要出典] チューリングは次のように述べた。

「関数が効果的に計算可能であるのは、その値が何らかの純粋に機械的なプロセスによって求められる場合である」と述べられています。これを文字通りに受け取ると、純粋に機械的なプロセスとは、機械によって実行できるプロセスであると理解できます。この開発により、計算可能性^†と効果的な計算可能性が同一視されるようになりました。[ ^†は上記の脚注です。] ^[15]

歴史

1930 年代の論理学者にとって重要な問題の一つは、デイヴィッド・ヒルベルトとヴィルヘルム・アッカーマンのEntscheidungsproblem ^[17]であった。これは、数学的真理を数学的虚偽から分離する機械的な手順があるかどうかを問うものであった。この探求には、「アルゴリズム」または「有効な計算可能性」という概念を、少なくとも探求を始めるのに十分な程度には明確に定義することが必要であった。^[¹⁸ ]^しかし^、アロンゾ・チャーチの試みは、最初から今日まで続く論争から始まった。^[19]「有効な計算可能性」という概念は、(i) 公理体系における「公理」なのか、(ii) 単に2 つ以上の命題を「特定」する定義なのか、(iii)自然現象の観察によって検証される経験的仮説なのか、それとも (iv)議論のための 提案(つまり「命題」) なのか [ 明確にする ]。

1930年～1952年頃

この問題の研究の過程で、チャーチと彼の学生スティーブン・クリーネはλ定義可能関数の概念を導入し、数論で頻繁に遭遇する関数のいくつかの大きなクラスがλ定義可能であることを証明することができた。^[20]議論は、チャーチがゲーデルに「効果的に計算可能な」関数をλ定義可能関数として定義すべきだと提案したときに始まった。しかし、ゲーデルは納得せず、その提案を「まったく不十分」だと言った。^[21]むしろ、チャーチとの書簡（1934年頃 - 1935年）の中で、ゲーデルは「効果的な計算可能性」の概念を公理化することを提案した。実際、1935年にクリーネに宛てた手紙の中で、チャーチは次のように報告している。

当時の彼（ゲーデル）の唯一の考えは、未定義の概念としての有効な計算可能性の観点から、この概念の一般に受け入れられている特性を具体化する公理の集合を述べ、それに基づいて何かを行うことが可能であるかもしれないというものだった。^[22]

しかしゲーデルはそれ以上の指針を与えなかった。結局、ゲーデルはヘルブランの提案によって修正された再帰を提案した。これはゲーデルが1934年にニュージャージー州プリンストンで行った講義で詳述したものだ（クリーネとロッサーがメモを書き留めた）。しかしゲーデルは、2つのアイデアが「発見的方法以外では」十分に識別できるとは考えていなかった。^[23]

次に、有効計算可能性の 2 つの概念の等価性を特定し証明する必要がありました。λ 計算と「一般的な」再帰法を駆使して、クリーネはチャーチとJ. バークレーロッサーの助けを借りて、2 つの計算が等価であることを示す証明 (1933、1935) を作成しました。チャーチはその後、ヘルブラン - ゲーデル再帰法を使用するように手法を修正し、次に Entscheidungsproblemが解決不可能であることを証明しました (1936)。つまり、適切に形成された式がベータ正規形を持つかどうかを判断できるアルゴリズムは存在しないということです。^[24]

ゲーデルは、何年も後にデイヴィスに宛てた手紙（1965年頃）の中で、「これらの（1934年の）講義の時点では、彼の再帰の概念がすべての可能な再帰を包含しているとは全く確信していなかった」と述べている。 ^[25] 1963年から1964年までに、ゲーデルはヘルブラン-ゲーデルの再帰とλ計算を否定し、チューリングマシンを「アルゴリズム」または「機械的手順」または「形式システム」の定義として支持した。^[26]

自然法則につながる仮説？ : 1936年後半、アラン・チューリングの論文（これもまた、Entscheidungsproblemが解決不可能であることを証明するもの）は口頭で発表されたが、まだ印刷物としては出版されていなかった。^[27]一方、エミール・ポストの1936年の論文は出版され、チューリングの研究とは独立していると認定された。^[28]ポストは、チャーチのλ計算と再帰による実効計算可能性の「同一視」に強く反対し、次のように述べた。

実際、チャーチらがすでに行った研究は、この特定を作業仮説の段階をはるかに超えたものにしています。しかし、この特定を定義の下に隠してしまうと、継続的な検証の必要性が見えなくなってしまいます。^[29]

むしろ、彼は「有効な計算可能性」という概念を、「定義や公理」ではなく、帰納的推論によって「自然法則」に導く可能性のある単なる「作業仮説」とみなした。 ^[30]この考えはチャーチによって「厳しく」批判された。^[31]

そのため、ポストは1936年の論文で、クルト・ゲーデルが1934年から1935年にかけてチャーチに提案した、この命題は公理または公理の集合として表現できるかもしれないという示唆も軽視していた。^[22]

チューリングは別の定義を加え、ロッサーはこれら 3 つを同等とみなしている。わずかの間に、チューリングの 1936-1937 年の論文「計算可能数について、その起因問題への応用」^[27]が発表された。その中で彼は、a マシン (現在ではチューリングマシン抽象計算モデルとして知られている) の導入とともに、「効果的な計算可能性」という別の概念を述べた。また、1936-1937 年の論文の「付録」として追加された証明スケッチで、チューリングは、λ 計算とチューリングマシンによって定義された関数のクラスが一致することを示した。^[32]チャーチは、チューリングの分析がいかに説得力があるかをすぐに認識した。チューリングの論文のレビューで、彼はチューリングの概念が「通常の (明示的に定義されていない) 意味での有効性との同一性をすぐに明らかにした」ことを明らかにした。^[33]

数年後（1939年）、チューリングは、それ以前のチャーチやクリーネと同様に、機械的計算エージェントの形式的な定義が正しいと提案しました。^[34]したがって、1939年までに、チャーチ（1934）とチューリング（1939）は、それぞれ「形式システム」は「効果的な計算可能性」の定義であるべきだと提案していました。 ^{[35]どちらも、自分の発言を}テーゼとして組み立てていませんでした。

ロッサー（1939）は、定義としての概念を3つ正式に特定しました。

これら3つの定義はすべて同等なので、どれを使用しても問題ありません。^[36]

クリーネはテーゼIを提案した。これにより「テーゼ」の明白な表現はクリーネに委ねられた。1943年にクリーネは「テーゼI」を提案した。^[37]

この経験的事実 [一般的な再帰関数は効果的に計算可能である] から、チャーチは次の命題を述べました。同じ命題は、チューリングの計算機の説明にも暗黙的に含まれています。
命題 I.あらゆる効果的に計算可能な関数（効果的に決定可能な述語）は一般再帰的である[Kleene の強調]
効果的に計算可能（効果的に決定可能）という用語の正確な数学的定義が欠けていたため、この論文をその定義として採用することができます...

...この命題は仮説の性格を持っている。これはポストとチャーチが強調した点である。命題とその逆を定義と考えると、仮説は定義から展開された数学理論の応用に関する仮説となる。この仮説を受け入れるには、すでに述べたように、非常に説得力のある根拠がある。

チャーチ＝チューリングのテーゼ：スティーブン・クリーネは、メタ数学入門で、最終的に、再帰的実現可能性の理論を用いて、「チャーチのテーゼ」と「チューリングのテーゼ」を正式に命名しました。クリーネは、チャーチ＝クリーネのラムダ定義可能性という用語から、ゲーデル＝クリーネの再帰性（部分的再帰関数）という用語に切り替えて研究を発表しました。この移行で、クリーネはゲーデルの一般再帰関数を修正し、EJ ブラウワーの直観主義の問題が解決不可能であることを証明できるようにしました。彼の大学院の論理学の教科書では、「チャーチのテーゼ」が紹介され、基本的な数学的結果が実現不可能であることが実証されています。次に、クリーネは「チューリングのテーゼ」を発表し、エミール・ポストの研究に基づくチューリングマシンの簡略化された導出を使用して、結果が計算不可能であることを示しています。両方の命題は「定理 XXX」の使用によって同等であることが証明されます。

命題I.あらゆる効果的に計算可能な関数（効果的に決定可能な述語）は一般再帰的である。^[38]

定理XXX：以下の部分関数のクラスは共存的である、すなわち同じメンバーを持つ：（a）部分再帰関数、（b）計算可能関数... ^[39]

チューリングのテーゼ：当然計算可能とみなされるすべての関数は、彼の定義、すなわち彼のマシンの1つによって計算可能であるというチューリングのテーゼは、定理XXXによるチャーチのテーゼと同等である。^[39]

最後に、クリーネは、ウィリアム・ブーンからの批判で求められたように、アラン・チューリングの論文「半群の相殺を伴う単語問題」の概念を明確にする一節で、初めて「チャーチ＝チューリングのテーゼ」という用語を使用している。^[40]

その後の展開

1980年、ロビン・ガンディ（チューリングの学生で友人）は「効果的な計算可能性」という概念をより深く理解しようと、機械計算（チューリングマシンによって実行される人間の計算とは対照的）を分析することになった。ガンディは、セルオートマトン（コンウェイのライフゲームを含む）、並列性、結晶オートマトンに興味を持ち、分析した結果、4つの「原理（または制約）」を提唱した。これは、あらゆる機械が満たさなければならないと主張されている。^[41]最も重要な4番目の原理「因果律」は、「効果と信号の伝播速度は有限である。現代物理学では、遠隔地での瞬間的な作用の可能性は否定されている」ことに基づいている。^[42]これらの原理といくつかの追加の制約（（1a）部品の線形寸法の下限、（1b）伝播速度（光速）の上限、（2）機械の離散的進行、（3）決定論的動作）から、彼は「原理IからIVを満たす装置によって計算できるものは計算可能である」という定理を生み出した。^[43]

1990年代後半、ウィルフリード・ジークはチューリングとガンディの「実効計算可能性」の概念を「非公式な概念を研ぎ澄まし、その一般的な特徴を公理的に定式化し、公理的な枠組みを調査する」目的で分析した。^{[44] 1997年と2002年の著作で、ジークは}コンピュータ（「機械的に進行する人間の計算エージェント」）の動作に関する一連の制約を提示している。これらの制約は次のように要約される。

「（B.1）（有界性）コンピュータが即座に認識できる記号構成の数には一定の上限がある。
「（B.2）（有界性）コンピュータが取り得る内部状態の数には一定の上限がある。
「（L.1）（局所性）コンピュータは、観測された記号構成の要素のみを変更できます。
「（L.2）（局所性）コンピュータは、ある記号構成から別の記号構成に注意を移すことができますが、新しく観測される構成は、直前に観測された構成から一定の距離内にある必要があります。
「（D）（決定性）直ちに認識可能な（サブ）構成は、次の計算ステップ（およびid [瞬間的な記述]）を一意に決定します。」別の言い方をすると、「コンピュータの内部状態と観測された構成を組み合わせることで、次の計算ステップと次の内部状態が一意に決定されます。」^[45]

この問題は学界で活発に議論されている。^[46]^[47]

定義としての論文

このテーゼは、単なる数学的定義にすぎないと見なすことができる。この主題に関するゲーデルのコメントはこの見解を示唆している。例えば、「機械的な計算可能性の正しい定義は、チューリングによって疑いの余地なく確立された」。^[48]このテーゼを単なる定義と見なす論拠は、ロバート・I・ソアレ^[5]によって明確に述べられており、そこでは、チューリングの計算可能性の定義は、連続関数のイプシロンデルタ定義と同じくらい正しい可能性が低いとも主張されている。

論文の成功

再帰、λ計算、チューリングマシン以外にも、効果的な計算可能性を記述するための形式論が提案されている。クリーネ（1952）は、クルト・ゲーデル（1936 ）の「システムS _1で計算可能な」関数と、エミール・ポスト（1943、1946）の「標準的な（通常の）システム」をリストに加えている。^[49] 1950年代に、ハオ・ワンとマーティン・デイビスは、 1つのテープのチューリングマシンモデルを大幅に簡略化した（ポストチューリングマシンを参照）。マービン・ミンスキーはこのモデルを2つ以上のテープに拡張し、テープを「アップダウンカウンター」に大幅に簡略化した。メルザックとランベックはこれをさらに発展させて、現在ではカウンターマシンモデルとして知られるモデルを考案した。 1960年代後半から1970年代前半にかけて、研究者たちはカウンターマシンモデルをレジスタマシンへと拡張した。レジスタマシンは現代のコンピュータの概念に近い。他のモデルには組み合わせ論理やマルコフアルゴリズムなどがある。グレヴィッチはコルモゴロフとウスペンスキーのポインタマシンモデル（1953、1958）を次のように付け加えている。「彼らはただ、計算可能関数の概念を拡張する方法はないということを自分たちに納得させたかっただけなのだ。」^[50]

これらの貢献はすべて、モデルが計算的にチューリングマシンと同等であることの証明を伴い、そのようなモデルはチューリング完全であると言われています。「有効な計算可能性/計算可能性」の概念を形式化するこれらのさまざまな試みはすべて同等の結果をもたらしたため、現在ではチャーチ＝チューリングのテーゼが正しいと一般に考えられています。実際、ゲーデル (1936) はこれよりも強力なものを提案しました。彼は、「S ₁で計算可能」という概念には「絶対的な」ものがあると指摘しました。

_{また、システム S i}の 1 つ、または超限型のシステムで計算可能な関数は、S ₁でもすでに計算可能 [計算可能] であることが示されることもあります。したがって、「計算可能」 [計算可能] という概念は、ある明確な意味で「絶対的」ですが、他のよく知られたメタ数学的概念 (たとえば、証明可能、定義可能など) は、実質的に、それらが定義されているシステムに大きく依存しています... ^[51]

証明における非公式な用法

計算可能性理論の証明では、関数の計算可能性を証明するために、厳密で形式的な証明に含まれる（多くの場合非常に長い）詳細を避けながら、チャーチ＝チューリングのテーゼを非公式な方法で引用することがよくあります。^[52]関数がチューリングマシンによって計算可能であることを証明するには、通常、関数を効果的に計算する方法を非公式な英語で説明し、「チャーチ＝チューリングのテーゼにより」関数がチューリング計算可能（つまり、部分再帰的）であると結論付ければ十分であると考えられています。

ディルク・ファン・ダーレンはチャーチ＝チューリングのテーゼの非公式な使用を説明するために次のような例を挙げている。^[53]

例: 各無限再帰可算(RE) 集合には、無限再帰集合が含まれます。
証明: A を無限 RE とします。A の要素を n ₀、 n ₁、 n ₂、 n ₃、... とリストします。
このリストから増加するサブリストを抽出します。m ₀ = n ₀とし、有限回数ステップ実行した後、 n _k > m ₀となるn _{k を}見つけ、m ₁ = n _kとします。この手順を繰り返して、m ₂ > m _{1などを見つけます。これにより、m}_i < m _i+1という特性を持つ、A のサブセット B={m ₀、m ₁、m ₂ 、...} の有効なリストが生成されます。

主張。B は決定可能である。なぜなら、B の k をテストするためには、ある i について k = mi であるかどうかをチェックする必要があるからである_。m_iのシーケンスは増加しているので、リストの要素を最大で k+1 個生成し、それらを k と比較する必要がある。それらのどれも k に等しくない場合、k は B に含まれない。このテストは有効であるため、B は決定可能であり、チャーチのテーゼにより再帰的である。

上記の例を完全に厳密にするためには、チューリングマシンまたは λ 関数を注意深く構築するか、再帰公理を注意深く適用するか、せいぜい計算可能性理論のさまざまな定理を巧みに適用する必要があります。しかし、計算可能性理論家は、チューリング計算可能性が効果的に計算できるものを正しく捉えていると信じており、集合 B を決定するための効果的な手順が英語で説明されているため、計算可能性理論家はこれを集合が実際に再帰的であることの証拠として受け入れます。

バリエーション

チャーチ＝チューリングのテーゼの成功により、テーゼのバリエーションが提案されるようになった。例えば、物理的なチャーチ＝チューリングのテーゼは「物理的に計算可能な関数はすべてチューリング計算可能である」と述べている。^[54]^{: 101}

チャーチ＝チューリングのテーゼは、ある計算モデルが他の計算モデルをシミュレートできる効率については何も述べていない。例えば、（マルチテープ）汎用チューリングマシンは、どのチューリングマシンをシミュレートする場合も対数的な減速係数しか発生しないことが証明されている。^[55]

チャーチ＝チューリングのテーゼのバリエーションは、任意だが「合理的な」計算モデルが効率的にシミュレートできるかどうかを扱っている。これは実現可能性テーゼと呼ばれ、^{[56] （}古典的な）複雑性理論的チャーチ＝チューリングのテーゼ、あるいは拡張チャーチ＝チューリングのテーゼとも呼ばれ、チャーチやチューリングによるものではなく、複雑性理論の発展の中で徐々に実現されたものである。それは次のように述べている。^[57]「確率的チューリングマシンは、あらゆる現実的な計算モデルを効率的にシミュレートできる。」ここでの「効率的に」という言葉は、多項式時間の削減までを意味する。このテーゼはもともと、イーサン・バーンスタインとウメシュ・ヴァジラニ（1997年）によって計算複雑性理論的チャーチ＝チューリングのテーゼと呼ばれていた。複雑性理論的チャーチ＝チューリングのテーゼは、すべての「合理的な」計算モデルは、多項式時間で計算できる同じクラスの問題を生み出すと仮定している。確率的多項式時間 ( BPP ) が決定論的多項式時間 ( P ) に等しいという予想を仮定すると、複雑性理論のチャーチ＝チューリングのテーゼでは「確率的」という語は省略可能となる。不変性テーゼと呼ばれる同様のテーゼは、シース・F・スロットとピーター・ファン・エムデ・ボアスによって提唱された。それは「『合理的な』マシンは、多項式的に制限された時間的オーバーヘッドと定数倍の空間的オーバーヘッドの範囲内で、互いをシミュレートできる」と述べている。 ^{[58]このテーゼはもともと}STOC '84の論文で発表されたもので、チューリングマシン上でのランダムアクセスマシンのシミュレーションで多項式時間オーバーヘッドと定数倍の空間オーバーヘッドを同時に達成できることを示した最初の論文であった。^[59]

BQP がBPPの厳密なスーパーセットであることが示されれば、複雑性理論のチャーチ＝チューリングのテーゼは無効になります。言い換えれば、効率的な確率アルゴリズムを持たないタスクを実行する効率的な量子アルゴリズムが存在することになります。ただし、量子コンピュータは常にチューリングマシンでシミュレートできるため、元のチャーチ＝チューリングのテーゼは無効になりませんが、効率性の理由から、古典的な複雑性理論のチャーチ＝チューリングのテーゼは無効になります。その結果、量子複雑性理論のチャーチ＝チューリングのテーゼは次のように述べています。^[57]「量子チューリングマシンは、あらゆる現実的な計算モデルを効率的にシミュレートできます。」

ユージン・エーベルバッハとピーター・ウェグナーは、チャーチ＝チューリングのテーゼは広く解釈されすぎることがあると主張し、「チューリングマシンはアルゴリズムの振る舞いを表現するが、アルゴリズムが計算可能なものを正確に捉えるというより広い主張は無効である」と述べている^[60] 。彼らは、このテーゼで捉えられていない計算形式が今日でも重要であり、それをスーパーチューリング計算と呼んでいると主張している。

哲学的含意

哲学者たちは、チャーチ＝チューリングのテーゼが心の哲学に影響を与えると解釈してきた。^[61]^[62]^[63] B・ジャック・コープランドは、長期的にはチューリングマシンによるシミュレーションを逃れる実際の決定論的な物理プロセスが存在するかどうかは経験的な未解決の問題であると述べている。さらに、そのようなプロセスが人間の脳の働きに関与しているかどうかも経験的な未解決の問題であると述べている。^[64]チャーチ＝チューリングのテーゼと物理学との関係、およびハイパーコンピューティングの可能性をカバーする重要な未解決の問題もいくつかある。物理学に適用された場合、このテーゼにはいくつかの意味が考えられる。

宇宙はチューリングマシンと同等であるため、非再帰関数を計算することは物理的に不可能です。これは強いチャーチ＝チューリングのテーゼ、またはチャーチ＝チューリング＝ドイチュの原理と呼ばれ、デジタル物理学の基礎となっています。
宇宙はチューリングマシンと同等ではありません (つまり、物理法則はチューリング計算可能ではありません) が、計算不可能な物理的イベントはハイパーコンピュータの構築に「利用可能」ではありません。たとえば、計算可能な実数ではなくランダムな実数が物理学に関係する宇宙は、このカテゴリに分類されます。
宇宙はハイパーコンピュータであり、この特性を利用して非再帰関数を計算する物理装置を構築することは可能である。例えば、量子チューリングマシンなどの厳密なモデルは決定論的チューリングマシンと同等であることが知られているが、すべての量子力学的イベントがチューリング計算可能かどうかは未解決の問題である。（それらは必ずしも効率的に同等ではない。上記を参照。）ジョン・ルーカスとロジャー・ペンローズは、人間の心はある種の量子力学的に強化された「非アルゴリズム的」計算の結果である可能性があると示唆している。^[65]^[66]

これら 3 つのカテゴリの外側または中間に位置する技術的な可能性は他にも多数ありますが、これらは概念の範囲を示すのに役立ちます。

物理的コンピュータと生物学的コンピュータの両方に関するこの論文の哲学的側面は、オディフレディの1989年の再帰理論の教科書でも議論されている。^[67]^{: 101–123}

計算不可能な関数

計算不可能な関数を正式に定義することもできます。そのような関数のよく知られた例としては、ビジービーバー関数があります。この関数は入力nを受け取り、入力なしで実行した場合に、 n個の状態を持つチューリングマシンが停止する前に出力できる記号の最大数を返します。ビジービーバー関数の上限を見つけることは、チューリングマシンでは解決できない問題である停止問題を解くことと同じです。ビジービーバー関数はチューリングマシンでは計算できないため、チャーチ-チューリングのテーゼでは、この関数はどのような方法でも効果的に計算できないと述べられています。

いくつかの計算モデルは、（チャーチ＝チューリングの）計算不可能な関数の計算を可能にする。これらはハイパーコンピュータとして知られている。マーク・バージンは、帰納的チューリングマシンなどの超再帰アルゴリズムはチャーチ＝チューリングのテーゼを反証すると主張している。 ^[68]^[要出典]彼の議論は、通常のものよりも広いアルゴリズムの定義に依存しており、そのため、一部の帰納的チューリングマシンから得られる計算不可能な関数は計算可能と呼ばれている。チャーチ＝チューリングのテーゼのこの解釈は、上で説明した計算可能性理論で一般的に受け入れられている解釈とは異なる。超再帰アルゴリズムがチャーチ＝チューリングのテーゼの意味でアルゴリズムであるという議論は、計算可能性研究コミュニティ内で広く受け入れられていない。^[要出典]

参照

抽象機械
構成的数学におけるチャーチの論文
チャーチ・チューリング・ドイチュ原理は、あらゆる物理プロセスは汎用的な計算装置でシミュレートできるというものである。
計算可能性ロジック
計算可能性理論
決定可能性
ハイパーコンピューティング
計算モデル
Oracle（コンピュータサイエンス）
超再帰アルゴリズム
チューリング完全性

脚注

^ Robert Soare、「チューリングオラクルマシン、オンラインコンピューティング、および計算可能性理論における3つの変位」
^ Rabin, Michael O. (2012年6月). チューリング、チャーチ、ゲーデル、計算可能性、複雑性、ランダム化: 個人的な見解。イベントは9:36に発生します。 2021年12月5日閲覧。
^ アロンゾ・チャーチ文書に記されたマックス・ニューマンとチャーチの書簡
^チューリング、アラン (2004)。『チューリングの真髄：コンピューティング、論理、哲学 、人工知能、人工生命に関する重要な著作、そしてエニグマの秘密』（PDF）。オックスフォード：クラレンドン・プレス。p. 44。ISBN 9780198250791. 2021年12月6日閲覧。
^ ab Soare, Robert I. (1996 年 9 月). 「計算可能性と再帰」. Bulletin of Symbolic Logic . 2 (3): 284–321. CiteSeerX 10.1.1.35.5803 . doi :10.2307/420992. JSTOR 420992. S2CID 5894394.
^ チャーチの論文は1935年4月19日にアメリカ数学会に提出され、1936年4月15日に出版された。自身の結果を書き上げるのにかなりの進歩を遂げていたチューリングは、出版時にチャーチの証明を知って失望した。^[3]^[4]チューリングはすぐに論文を書き上げ、出版を急いだ。それは1936年5月28日にロンドン数学会の会報に受理され、1936年11月12日に発表され、シリーズ2、第42巻（1936-1937年）に掲載された。それは2つのセクションに掲載された：第3部（230-240ページ）は1936年11月30日に発行され、第4部（241-265ページ）は1936年12月23日に発行された。チューリングは第43巻（1937年）の544-546ページで訂正を加えた。^[5]^{: 45}
^ 教会 1936a
^ クリーネ 1936
^ チューリング 1937a
^ クリーネ 1936
^ チューリング 1937b. 証明の概要は153ページにあります: ^[10] $\lambda {\mbox{-definable}}$ ${\stackrel {triv}{\implies }}$ $\lambda {\mbox{-}}K{\mbox{-definable}}$ ${\stackrel {160}{\implies }}$ ${\mbox{Turing computable}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ $\lambda {\mbox{-definable}}$
^ Rosser 1939、Davis 1965:225 より。
^ 「効果的」。メリアム・ウェブスター大学用新辞典（第9版）。
^ 「effective」も参照。Merriam-Webster's Online Dictionary (第11版) 。2014年7月26日閲覧。また、この文献では「effective」の定義も示されています。最初の定義 [「決定的な、決定的な、または望ましい効果を生み出す」] は、「effective」という単語の意味「1a」の定義として、2 番目の定義 [「結果を生み出すことができる」] は、「EFFECTIVE」の同義語の説明 (導入部分で、「effective」、「effectual」、「efficient」、「efficacious」という単語の意味の類似点を要約) の一部として提供されています。
^ ab Turing, AM (1938). Systems of Logic Based on Ordinals (PDF) (PhD). Princeton University. p. 8. 2012-10-23 のオリジナル(PDF)からアーカイブ。2012-06-23に閲覧。
^ Gandy (1980:123) は次のように述べている:効果的に計算可能なものは計算可能である。彼はこれを「チャーチのテーゼ」と呼んでいる。
^ David Hilbert および Wilhelm Ackermann: Grundzüge der theoretischen Logik、ベルリン、ドイツ、Springer、第 1 版1928. (第 6 版、1972 年、ISBN 3-540-05843-5 ) 英語翻訳: David Hilbert and Wilhelm Ackermann: Principles of Mathematical Logic、AMS Chelsea Publishing、プロビデンス、ロードアイランド、米国、1950 年。
^ デイビスのチャーチ1936年以前の解説書「初等数論の解決不可能な問題」デイビス1965:88。チャーチは100ページ以降で「有効な計算可能性」という言葉を使用している。
^アダム・オルゼフスキー他編『 70年後のチャーチのテーゼ』 (2006年)のレビューで、ピーター・スミスはムラーフスキーとウォレンスキーの論文を批判し、チャーチ＝チューリングのテーゼの地位について4つの「線」を示唆している。(1) 経験的仮説 (2) 公理または定理 (3) 定義 (4) 説明。しかしスミスは、(4) は (3) と区別がつかないと述べている。スミス (2007-07-11) 『70年後のチャーチのテーゼ』 http://www.logicmatters.net/resources/pdfs/CTT.pdf を参照。
^ 参照: Church 1936a「初等数論の解決不可能な問題」 (Davis 1965:89)の脚注3。
^ ドーソン 1997:99.
^ ジーク 1997:160より。
^ Sieg 1997:160 は、1935 年にチャーチがクリーネに宛てて書いた手紙から引用している。Davis 1965:44 の Gödel 1934 の脚注 3 を参照。
^ 参照: Church 1936 in Davis 1965:105ff..
^ ゲーデル1934以前のデイビスの解説、デイビス1965:40。
^ ゲーデルが計算モデルとしてチューリングの機械を採用したことに関する詳細な議論については、Shagrir, Oron (2006-06-15) を参照。「ゲーデルとチューリングの計算可能性」(PDF)。70年後のチャーチの論文。De Gruyter。pp. 393–419。doi :10.1515 / 9783110325461.393。ISBN 978-3-11-032494-5. 2015年12月17日時点のオリジナル（PDF）からアーカイブ。2016年2月8日閲覧。
^ チューリング 1937aより。
^ cf. 編集者による1936年以降の 「有限組み合わせ過程。定式化I」の脚注、Davis 1965:289。
^ Davis 1965:291、脚注8の1936年以降。
^ Davis 1952:291の1936年以降。
^ ジーク 1997:171 および 176–177。
^ Turing 1936–1937、Davis 1965:263ff. より。
^ 教会 1937年。
^ Turing 1939、Davis:160 ページ。
^ 参照: Church 1934 in Davis 1965:100、また Turing 1939 in Davis 1965:160。
^ 強調追加、Rosser 1939、Davis 1965:226。
^ Kleene 1943、p. 60、Davis 1965:274。脚注は省略。
^ クリーネ1952:300.
^クリーネ1952:376より。
^ クリーネ 1952:382, 536
^ ガンディ 1980:123ff.
^ ガンディ 1980:135
^ ガンディ 1980:126
^ Sieg 1998–1999 in Sieg, Sommer & Talcott 2002:390ff.;ジーク 1997:154ff とも。
^ 脚注で、Sieg は Post の 1936 年の (B) を (B.1) と (B.2) に、(L) を (L.1) と (L.2) に分割し、(D) を別の方法で説明しています。彼が提案した Gandy マシンに関しては、後に LC.1、LC.2、GA.1、GA.2 を追加しています。これらは複雑です。Sieg、Sommer、Talcott 2002:390ff の Sieg 1998–1999 を参照してください。
^ 論文集は Olszewski, Woleński & Janusz (2006) に掲載されています。また、この論文集のレビューは、Smith, Peter (2007-07-11) の「70 年後の教会の論文」(PDF) に掲載されています。
^ Hodges, Andrew (2005)も参照。「チャーチとチューリングは機械についての論文を持っていたか？」(PDF) 。 2016年3月4日時点のオリジナル(PDF)からアーカイブ。 2014年7月27日閲覧。
^ ゲーデル、クルト(1995) [193?]。「決定不可能なディオファントス命題」。フェファーマン、ソロモン(編)。全集。第3巻。ニューヨーク：オックスフォード大学出版局。p. 168。ISBN 978-0-19-507255-6. OCLC 928791907.
^ クリーネ 1952:320
^ グレヴィッチ 1988:2
^ ゲーデル（1936年）のデイヴィス訳『決定不能』 p. 83、クリーネ（1952年）p. 321の翻訳では「計算可能な」という単語の使い方が異なっている。
^ Horsten、Olszewski、Woleński、Janusz 2006:256。
^ ガベイ 2001:284
^ Piccinini, Gualtiero (2007 年 1 月). 「計算主義、チャーチ＝チューリングのテーゼ、そしてチャーチ＝チューリングの誤謬」(PDF) . Synthese . 154 (1): 97–120. CiteSeerX 10.1.1.360.9796 . doi :10.1007/s11229-005-0194-z. S2CID 494161. 2008 年 4 月 24 日のオリジナルからアーカイブ(PDF) 。
^アローラ、サンジーヴ 、バラク、ボアズ（2009）。複雑性理論：現代的アプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4。セクション 1.4「文字列としてのマシンと汎用チューリングマシン」および 1.7「定理 1.9 の証明」。
^ 「公式問題説明」(PDF)。2005年11月24日時点のオリジナル(PDF)からアーカイブ。
^ ab ケイ、フィリップ、ラフラム、レイモンド、モスカ、ミシェル (2007)。量子コンピューティング入門。オックスフォード大学出版局。pp. 5–6。ISBN 978-0-19-857049-3。
^ van Emde Boas, Peter (1990). 「マシンモデルとシミュレーション」.理論計算機科学ハンドブック A. Elsevier . p. 5.
^ Slot, C.; van Emde Boas, P. (1984 年 12 月)。テープ対コア: 空間効率の高い完全ハッシュ関数の空間不変性への応用。STOC 。
^ エーベルバッハとウェグナー、2003、p. 287.
^ Abramson, Darren (2011). 「心の哲学は（部分的には）コンピュータサイエンスの哲学である」. Minds and Machines . 21 (2): 203–219. doi :10.1007/s11023-011-9236-0. S2CID 32116031.
^ Copeland, B. Jack (2017-11-10). 「チャーチ＝チューリングのテーゼ」。Zalta , Edward N. (編)。スタンフォード哲学百科事典。
^ 原著論文を見つけるには、Chalmers, David J.編著 (2002) 「Philosophy of Mind: Classical and Contemporary Readings」を参照してください。ニューヨーク: Oxford University Press。ISBN 978-0-19-514581-6. OCLC 610918145.
^ Copeland, B. Jack (2004)。「計算」。Floridi , Luciano (編)。コンピューティングと情報の哲学に関するブラックウェルガイド。Wiley-Blackwell。p. 15。ISBN 978-0-631-22919-3。
^ 参照：ペンローズ、ロジャー（1990年）。「アルゴリズムとチューリングマシン」。皇帝の新しい心：コンピュータ、心、物理法則について。オックスフォード：オックスフォード大学出版局。pp. 47–49。ISBN 978-0-19-851973-7. OCLC 456785846.
^ また、「数学的洞察の非アルゴリズム的性質」の説明、ロジャー・ペンローズ(1990)。「心の物理学はどこにあるのか?」。皇帝の新しい心: コンピューター、心、物理法則について。オックスフォード: オックスフォード大学出版局。pp. 416–418。ISBN 978-0-19-851973-7. OCLC 456785846.
^ Piergiorgio Odifreddi (1989)。古典的再帰理論。論理学および数学の基礎研究。第125巻。アムステルダム、オランダ：北ホラント州。
^ Burgin, Mark (2005).超再帰アルゴリズム. コンピュータサイエンスのモノグラフ. ニューヨーク: Springer. ISBN 978-0-387-95569-8. OCLC 990755791.

参考文献

バーワイズ、ジョン、ケイスラー、HJ、クネン、ケネス、編 (1980)。クリーネシンポジウム。アムステルダム：ノースホランド出版社。ISBN 978-0-444-85345-5。
Ben-Amram, AM (2005). 「チャーチ＝チューリングのテーゼとその類似物」SIGACT News . 36 (3): 113–116. CiteSeerX 10.1.1.74.7308 . doi :10.1145/1086649.1086651. S2CID 13566703. 2017-07-06 にオリジナル(PS)からアーカイブ。2017-10-24に取得。
バーンスタイン、E.米国ワジラニ (1997)。「量子複雑性理論」。SIAM ジャーナルオンコンピューティング。26 (5): 1411–1473。CiteSeerX 10.1.1.655.1186。土井：10.1137/S0097539796300921。
Blass, Andreas ; Gurevich, Yuri (2003 年 10 月)。「アルゴリズム: 絶対的な定義の探求」(PDF)。欧州理論計算機科学協会紀要(81)。2004年 7 月 27 日のオリジナルからアーカイブ(PDF) 。^{[ページが必要]}
Burgin, Mark (2005)。「超再帰アルゴリズム」。コンピュータサイエンスのモノグラフ。Springer。ISBN 978-0-387-95569-8。
チャーチ、アロンゾ(1932) 。「論理の基礎となる公準」。数学年報。33 (2): 346–366。doi :10.2307/1968337。JSTOR 1968337。
Church, Alonzo (1936a年4月). 「初等数論の解決不可能な問題」(PDF) . American Journal of Mathematics . 58 (2): 345–363. doi :10.2307/2371045. JSTOR 2371045. S2CID 14181275. 2020年2月27日時点のオリジナル(PDF)からアーカイブ。
チャーチ、アロンゾ (1936b年6 月)。「Entscheidungsproblem に関するノート」。Journal of Symbolic Logic。1 ( 1 ): 40–41。doi :10.2307/2269326。JSTOR 2269326。S2CID 42323521 。
チャーチ、アロンゾ (1937年3 月)。「レビュー: AM チューリング、計算可能数について、その Entscheidungsproblem への応用」。Journal of Symbolic Logic。2 ( 1 ): 42–43。doi :10.2307/2268810。JSTOR 2268810。
チャーチ、アロンゾ (1941)。ラムダ変換の計算。プリンストン：プリンストン大学出版局。
Cooper, SB; Odifreddi, P. (2003)。「自然における計算不可能性」。SB Cooper、SS Goncharov (編)。計算可能性とモデル: 東西の視点。Kluwer Academic/Plenum Publishers。pp. 137–160。
デイビス、マーティン編 (1965)。『決定不能、決定不能な命題、解決不能な問題、計算可能な関数に関する基本論文』ニューヨーク：レイヴン・プレス。このセクションで言及されているゲーデル、チャーチ、チューリング、ロッサー、クリーネ、ポストによるオリジナルの論文が含まれています。
ドーソン、ジョン W. ジュニア (1997)。論理的ジレンマ: クルト・ゲーデルの生涯と業績。マサチューセッツ州ウェルズリー、米国: AK ピーターズ。
Eberbach, E.; Wegner, P. (2003 年 10 月). 「チューリングマシンを超えて」(PDF) . Bulletin of the European Association for Theoretical Computer Science (81): 279–304. CiteSeerX 10.1.1.61.9759 . 2016 年 3 月 15 日のオリジナルからアーカイブ(PDF) 。
ガバイ、DM（2001）。哲学論理ハンドブック。第1巻（第2版）。
ガンディ、ロビン(1980)。「チャーチのテーゼとメカニズムの原理」。HJ バーワイズ、HJ キースラー、K. クネン (編)。クリーネシンポジウム。ノースホランド出版社。pp. 123–148。
ガンディ、ロビン（1994）。ヘルケン、ロルフ（編）。普遍的なチューリングマシン: 半世紀にわたる調査。ニューヨーク: ウィーン・シュプリンガー・フェルラーク。 51ページ以降。ISBN 978-3-211-82637-9。
ゲーデル、クルト (1965) [1934]。「形式数学システムの決定不可能な命題について」。デイビス、マーティン (編) 『決定不可能な命題』。クリーネとロッサー (講義ノートテイカー)、高等研究所 (講義スポンサー)。ニューヨーク: レイヴンプレス。
ゲーデル、クルト (1936)。「Über die Lāange von Beweisen」[証明の長さについて]。Ergenbnisse Eyenes Mathematishen Kolloquiums (ドイツ語) (7)。身長：23～24。Kleene (1952) による引用。
Gurevich, Yuri (1988 年 6 月). 「コルモゴロフマシンと関連する問題について」.欧州理論計算機科学協会紀要(35): 71–82.
Gurevich, Yuri (2000 年 7 月). 「Sequential Abstract State Machines Capture Sequential Algorithms」(PDF) . ACM Transactions on Computational Logic . 1 (1): 77–111. CiteSeerX 10.1.1.146.3017 . doi :10.1145/343369.343384. S2CID 2031696. 2003-10-16 にオリジナルからアーカイブ(PDF)されました。
ヘルブランド、ジャック（1932年）。「数学における無矛盾性」。Journal für die Reine und Angewandte Mathematik (フランス語)。166 : 1-8.土井：10.1515/crll.1932.166.1。S2CID 116636410。
ホフスタッター、ダグラス R. (1999-02-05)。「第 17 章: チャーチ、チューリング、タルスキ、その他」。ゲーデル、エッシャー、バッハ: 永遠の黄金の編み紐(20 周年記念版)。ベーシックブックス。559 ～ 585 ページ。ISBN 0-465-02656-7。
クリーネ、スティーブン・コール（1935年1月）。「形式論理における正の整数の理論」。アメリカ数学ジャーナル。57（1）：153–173＆219–244。doi ：10.2307 / 2372027。JSTOR 2372027。
クリーネ、スティーブン・コール (1936)。「ラムダ定義可能性と再帰性」デューク数学ジャーナル。2 (2): 340–353。doi :10.1215/s0012-7094-36-00227-2 。
クリーネ、スティーブン・コール( 1943)。「再帰述語と量指定子」。アメリカ数学会誌。53 (1): 41–73。doi : 10.2307/ 1990131。JSTOR 1990131 。『The Undecidable』255ページ以降に再録。クリーネは「一般再帰」の定義を洗練し、「12. アルゴリズム理論」の章で「テーゼ I」(274ページ) を提唱した。彼は後にこのテーゼを繰り返し(クリーネ 1952:300)、「チャーチのテーゼ」(クリーネ 1952:317) (つまりチャーチのテーゼ) と名付けた。
クリーネ、スティーブン・コール（1952）。メタ数学入門。ノースホランド。OCLC 523942。
Knuth, Donald (1973)。『コンピュータプログラミングの芸術』第 1 巻/基本アルゴリズム (第 2 版)。Addison–Wesley。
Kugel, Peter (2005 年 11 月)。「計算の枠を超えて考える時が来た」。Communications of the ACM。48 ( 11 ): 32–37。CiteSeerX 10.1.1.137.6939。doi : 10.1145 /1096000.1096001。S2CID 29843806。
Lewis, HR ; Papadimitriou, CH (1998). 『計算理論の要素』アッパーサドルリバー、ニュージャージー州、米国: Prentice-Hall.
マンナ、ゾハール（2003）[1974]。計算の数学的理論。ドーバー。ISBN 978-0-486-43238-0。{{cite book}}: CS1 maint: location missing publisher (link)
マルコフ、AA （1960）[1954]。「アルゴリズムの理論」アメリカ数学会翻訳。2 （15）：1–14。
オルシェフスキ、アダム、ウォレンスキ、ロバート、ヤヌシュ編 (2006)。『70年後のチャーチのテーゼ』フランクフルト：オントス。ISBN 978-3-938793-09-1. OCLC 909679288.
Pour-El, MB ; Richards, JI (1989).解析と物理学における計算可能性. Springer Verlag .
Rosser , JB ( 1939)。「ゲーデルの定理とチャーチの定理の証明の非公式な解説」。The Journal of Symbolic Logic。4 ( 2): 53–60。doi :10.2307/2269059。JSTOR 2269059。S2CID 39499392 。
ジーク、ウィルフリード、ソマー、リチャード、タルコット、キャロリン編 (2002)。数学の基礎に関する考察:ソロモン・フェファーマンに敬意を表したエッセイ。論理学講義ノート。第 15 巻。AKピーターズ社 ISBN 978-1-56881-169-7。
シロポロス、アポストロス (2008)。ハイパーコンピューティング：教会とチューリングの壁を越えたコンピューティング。シュプリンガー。ISBN 978-0-387-30886-9。
チューリング、AM (1937a) [1936 年 11 月に協会に提出]、「計算可能数について、その応用として、計算問題」(PDF)、ロンドン数学会紀要、2、第 42 巻、pp. 230–265、doi :10.1112/plms/s2-42.1.230、S2CID 73712およびチューリング、AM ( 1938)。「計算可能数について、その計算問題への応用: 訂正」。ロンドン数学会紀要。2. 第 43 巻 (1937 年発行)。pp. 544–546。doi :10.1112/plms/s2-43.6.544。（Davis 1965:115ffも参照）
チューリング、アラン・マシソン (1937b 年 12 月)。「計算可能性と λ-定義可能性」( PDF)。Journal of Symbolic Logic。2 ( 4): 153–163。doi :10.2307/2268280。JSTOR 2268280。S2CID 2317046。2020年 8月9 日のオリジナル(PDF)からアーカイブ。

外部リンク

スタンフォード哲学百科事典のB. ジャックコープランドによる「チャーチ＝チューリングのテーゼ」の項目。
スタンフォード哲学百科事典のGualtiero Piccininiによる「物理システムにおける計算」の項目— 関連する問題を包括的に哲学的に扱っています。
カズナチェフ、アルテム (2014-09-11). 「超越論的観念論とポストのチャーチ＝チューリングのテーゼの変種」.シンボリックロジックジャーナル. 1 (3): 103–105.
ノートルダム形式論理学ジャーナルの特別号（第28巻第4号、1987年）はチャーチ＝チューリングのテーゼを特集した。

[1] Robert Soare、「チューリングオラクルマシン、オンラインコンピューティング、および計算可能性理論における3つの変位」

[2] Rabin, Michael O. (2012年6月). チューリング、チャーチ、ゲーデル、計算可能性、複雑性、ランダム化: 個人的な見解。イベントは9:36に発生します。 2021年12月5日閲覧。

[TuringNewman-3] アロンゾ・チャーチ文書に記されたマックス・ニューマンとチャーチの書簡

[EssentialTuring-4] ^チューリング、アラン (2004)。『チューリングの真髄：コンピューティング、論理、哲学 、人工知能、人工生命に関する重要な著作、そしてエニグマの秘密』（PDF）。オックスフォード：クラレンドン・プレス。p. 44。ISBN 9780198250791. 2021年12月6日閲覧。

[Soare-5] Soare, Robert I. (1996 年 9 月). 「計算可能性と再帰」. Bulletin of Symbolic Logic . 2 (3): 284–321. CiteSeerX 10.1.1.35.5803 . doi :10.2307/420992. JSTOR 420992. S2CID 5894394.

[TuringLearn-6] チャーチの論文は1935年4月19日にアメリカ数学会に提出され、1936年4月15日に出版された。自身の結果を書き上げるのにかなりの進歩を遂げていたチューリングは、出版時にチャーチの証明を知って失望した。^[3]^[4]チューリングはすぐに論文を書き上げ、出版を急いだ。それは1936年5月28日にロンドン数学会の会報に受理され、1936年11月12日に発表され、シリーズ2、第42巻（1936-1937年）に掲載された。それは2つのセクションに掲載された：第3部（230-240ページ）は1936年11月30日に発行され、第4部（241-265ページ）は1936年12月23日に発行された。チューリングは第43巻（1937年）の544-546ページで訂正を加えた。^[5]^{: 45}

[7] 教会 1936a

[8] クリーネ 1936

[9] チューリング 1937a

[10] クリーネ 1936

[11] チューリング 1937b. 証明の概要は153ページにあります: ^[10] $\lambda {\mbox{-definable}}$ ${\stackrel {triv}{\implies }}$ $\lambda {\mbox{-}}K{\mbox{-definable}}$ ${\stackrel {160}{\implies }}$ ${\mbox{Turing computable}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ $\lambda {\mbox{-definable}}$

[12] Rosser 1939、Davis 1965:225 より。

[13] 「効果的」。メリアム・ウェブスター大学用新辞典（第9版）。

[14] 「effective」も参照。Merriam-Webster's Online Dictionary (第11版) 。2014年7月26日閲覧。また、この文献では「effective」の定義も示されています。最初の定義 [「決定的な、決定的な、または望ましい効果を生み出す」] は、「effective」という単語の意味「1a」の定義として、2 番目の定義 [「結果を生み出すことができる」] は、「EFFECTIVE」の同義語の説明 (導入部分で、「effective」、「effectual」、「efficient」、「efficacious」という単語の意味の類似点を要約) の一部として提供されています。

[Turing_1938_thesis_p8-15] Turing, AM (1938). Systems of Logic Based on Ordinals (PDF) (PhD). Princeton University. p. 8. 2012-10-23 のオリジナル(PDF)からアーカイブ。2012-06-23に閲覧。

[16] Gandy (1980:123) は次のように述べている:効果的に計算可能なものは計算可能である。彼はこれを「チャーチのテーゼ」と呼んでいる。

[17] David Hilbert および Wilhelm Ackermann: Grundzüge der theoretischen Logik、ベルリン、ドイツ、Springer、第 1 版1928. (第 6 版、1972 年、ISBN 3-540-05843-5 ) 英語翻訳: David Hilbert and Wilhelm Ackermann: Principles of Mathematical Logic、AMS Chelsea Publishing、プロビデンス、ロードアイランド、米国、1950 年。

[18] デイビスのチャーチ1936年以前の解説書「初等数論の解決不可能な問題」デイビス1965:88。チャーチは100ページ以降で「有効な計算可能性」という言葉を使用している。

[19] ^アダム・オルゼフスキー他編『 70年後のチャーチのテーゼ』 (2006年)のレビューで、ピーター・スミスはムラーフスキーとウォレンスキーの論文を批判し、チャーチ＝チューリングのテーゼの地位について4つの「線」を示唆している。(1) 経験的仮説 (2) 公理または定理 (3) 定義 (4) 説明。しかしスミスは、(4) は (3) と区別がつかないと述べている。スミス (2007-07-11) 『70年後のチャーチのテーゼ』 http://www.logicmatters.net/resources/pdfs/CTT.pdf を参照。

[20] 参照: Church 1936a「初等数論の解決不可能な問題」 (Davis 1965:89)の脚注3。

[21] ドーソン 1997:99.

[sieg160-22] ジーク 1997:160より。

[23] Sieg 1997:160 は、1935 年にチャーチがクリーネに宛てて書いた手紙から引用している。Davis 1965:44 の Gödel 1934 の脚注 3 を参照。

[24] 参照: Church 1936 in Davis 1965:105ff..

[25] ゲーデル1934以前のデイビスの解説、デイビス1965:40。

[26] ゲーデルが計算モデルとしてチューリングの機械を採用したことに関する詳細な議論については、Shagrir, Oron (2006-06-15) を参照。「ゲーデルとチューリングの計算可能性」(PDF)。70年後のチャーチの論文。De Gruyter。pp. 393–419。doi :10.1515 / 9783110325461.393。ISBN 978-3-11-032494-5. 2015年12月17日時点のオリジナル（PDF）からアーカイブ。2016年2月8日閲覧。

[On_Computable-27] チューリング 1937aより。

[28] ^ cf. 編集者による1936年以降の 「有限組み合わせ過程。定式化I」の脚注、Davis 1965:289。

[29] Davis 1965:291、脚注8の1936年以降。

[30] Davis 1952:291の1936年以降。

[31] ジーク 1997:171 および 176–177。

[32] Turing 1936–1937、Davis 1965:263ff. より。

[33] 教会 1937年。

[34] Turing 1939、Davis:160 ページ。

[35] 参照: Church 1934 in Davis 1965:100、また Turing 1939 in Davis 1965:160。

[36] 強調追加、Rosser 1939、Davis 1965:226。

[Davis274-37] Kleene 1943、p. 60、Davis 1965:274。脚注は省略。

[38] クリーネ1952:300.

[Kleene_1952_p376-39] クリーネ1952:376より。

[40] クリーネ 1952:382, 536

[41] ガンディ 1980:123ff.

[42] ガンディ 1980:135

[43] ガンディ 1980:126

[44] Sieg 1998–1999 in Sieg, Sommer & Talcott 2002:390ff.;ジーク 1997:154ff とも。

[45] 脚注で、Sieg は Post の 1936 年の (B) を (B.1) と (B.2) に、(L) を (L.1) と (L.2) に分割し、(D) を別の方法で説明しています。彼が提案した Gandy マシンに関しては、後に LC.1、LC.2、GA.1、GA.2 を追加しています。これらは複雑です。Sieg、Sommer、Talcott 2002:390ff の Sieg 1998–1999 を参照してください。

[46] 論文集は Olszewski, Woleński & Janusz (2006) に掲載されています。また、この論文集のレビューは、Smith, Peter (2007-07-11) の「70 年後の教会の論文」(PDF) に掲載されています。

[47] Hodges, Andrew (2005)も参照。「チャーチとチューリングは機械についての論文を持っていたか？」(PDF) 。 2016年3月4日時点のオリジナル(PDF)からアーカイブ。 2014年7月27日閲覧。

[48] ゲーデル、クルト(1995) [193?]。「決定不可能なディオファントス命題」。フェファーマン、ソロモン(編)。全集。第3巻。ニューヨーク：オックスフォード大学出版局。p. 168。ISBN 978-0-19-507255-6. OCLC 928791907.

[49] クリーネ 1952:320

[50] グレヴィッチ 1988:2

[51] ゲーデル（1936年）のデイヴィス訳『決定不能』 p. 83、クリーネ（1952年）p. 321の翻訳では「計算可能な」という単語の使い方が異なっている。

[52] Horsten、Olszewski、Woleński、Janusz 2006:256。

[53] ガベイ 2001:284

[54] Piccinini, Gualtiero (2007 年 1 月). 「計算主義、チャーチ＝チューリングのテーゼ、そしてチャーチ＝チューリングの誤謬」(PDF) . Synthese . 154 (1): 97–120. CiteSeerX 10.1.1.360.9796 . doi :10.1007/s11229-005-0194-z. S2CID 494161. 2008 年 4 月 24 日のオリジナルからアーカイブ(PDF) 。

[55] ^アローラ、サンジーヴ 、バラク、ボアズ（2009）。複雑性理論：現代的アプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4。セクション 1.4「文字列としてのマシンと汎用チューリングマシン」および 1.7「定理 1.9 の証明」。

[56] 「公式問題説明」(PDF)。2005年11月24日時点のオリジナル(PDF)からアーカイブ。

[kaye-57] ケイ、フィリップ、ラフラム、レイモンド、モスカ、ミシェル (2007)。量子コンピューティング入門。オックスフォード大学出版局。pp. 5–6。ISBN 978-0-19-857049-3。

[58] van Emde Boas, Peter (1990). 「マシンモデルとシミュレーション」.理論計算機科学ハンドブック A. Elsevier . p. 5.

[59] Slot, C.; van Emde Boas, P. (1984 年 12 月)。テープ対コア: 空間効率の高い完全ハッシュ関数の空間不変性への応用。STOC 。

[60] エーベルバッハとウェグナー、2003、p. 287.

[61] Abramson, Darren (2011). 「心の哲学は（部分的には）コンピュータサイエンスの哲学である」. Minds and Machines . 21 (2): 203–219. doi :10.1007/s11023-011-9236-0. S2CID 32116031.

[62] Copeland, B. Jack (2017-11-10). 「チャーチ＝チューリングのテーゼ」。Zalta , Edward N. (編)。スタンフォード哲学百科事典。

[63] 原著論文を見つけるには、Chalmers, David J.編著 (2002) 「Philosophy of Mind: Classical and Contemporary Readings」を参照してください。ニューヨーク: Oxford University Press。ISBN 978-0-19-514581-6. OCLC 610918145.

[64] Copeland, B. Jack (2004)。「計算」。Floridi , Luciano (編)。コンピューティングと情報の哲学に関するブラックウェルガイド。Wiley-Blackwell。p. 15。ISBN 978-0-631-22919-3。

[65] 参照：ペンローズ、ロジャー（1990年）。「アルゴリズムとチューリングマシン」。皇帝の新しい心：コンピュータ、心、物理法則について。オックスフォード：オックスフォード大学出版局。pp. 47–49。ISBN 978-0-19-851973-7. OCLC 456785846.

[66] また、「数学的洞察の非アルゴリズム的性質」の説明、ロジャー・ペンローズ(1990)。「心の物理学はどこにあるのか?」。皇帝の新しい心: コンピューター、心、物理法則について。オックスフォード: オックスフォード大学出版局。pp. 416–418。ISBN 978-0-19-851973-7. OCLC 456785846.

[67] Piergiorgio Odifreddi (1989)。古典的再帰理論。論理学および数学の基礎研究。第125巻。アムステルダム、オランダ：北ホラント州。

[68] Burgin, Mark (2005).超再帰アルゴリズム. コンピュータサイエンスのモノグラフ. ニューヨーク: Springer. ISBN 978-0-387-95569-8. OCLC 990755791.