計算可能性理論 において、チャーチ＝チューリングのテーゼ [ a ] は、計算可能な関数 の性質に関するテーゼ である。このテーゼは、自然数 上の関数が 有効な方法 で計算できるのは、チューリングマシン で計算できる場合に限ると述べている。このテーゼは、アメリカの数学者アロンゾ・チャーチ とイギリスの数学者アラン・チューリング にちなんで名付けられた。計算可能な関数の厳密な定義がなされる以前は、数学者は紙と鉛筆による方法で計算可能な関数を説明するために、しばしば「実質的に計算可能」 という非公式な用語を使用していた。1930年代には、計算可能性 の概念を形式化する ために、いくつかの独立した試みが行われた。
1933年、クルト・ゲーデルは ジャック・エルブラン と共に、一般再帰関数 のクラスの定義を形式化した。それは、合成 、再帰 、最小化 に関して閉じている（引数の数を任意に指定できる）関数の最小クラスであり、ゼロ 、後継関数 、およびすべての射影 を含む。 1932年から1933年にかけて、[ 3 ] アロンゾ・チャーチはλ計算 と呼ばれる関数を定義する方法を考案した。λ計算の中で、彼はチャーチ数 と呼ばれる自然数の符号化を定義した。自然数上の関数は、対応するチャーチ数上の関数がλ計算の項で表せる場合、λ計算可能であると呼ばれる。 1935～36年に[ 7 ] 1936年、チャーチの研究を知る前に、アラン 。 チューリング は 、実質的に計算可能な関数はチューリング計算可能な関数として定義されるべきだと提案しました。 チャーチ[ 13 ] クリーネ [ 14 ] [ 15 ] [ 17 ] 一般再帰的で ある場合のみである、ということです。このことから、数学者やコンピュータ科学者は、計算可能性の概念はこれら3つの等価なプロセスによって正確に特徴付けられると考えるようになりました。その後、計算可能性を特徴付けるための他の形式的な試みによって、この考えがさらに強固になりました（下記参照） 。
一方、チャーチ＝チューリングのテーゼは、上記の3つの形式的に定義された計算可能関数のクラスが、実質的に計算可能な関数という非形式的な 概念と一致すると述べている。このテーゼはほぼ普遍的に受け入れられているものの、実質的な計算可能性という概念は非形式的に定義されているに過ぎないため、形式的に証明することはできない。
創始以来、このテーゼには様々なバリエーションが生じており、例えば、コンピュータが我々の宇宙で物理的に実現できるもの（物理的チャーチ＝チューリングのテーゼ ）や、効率的に計算できるもの（チャーチ＝チューリングのテーゼ（計算複雑性理論） ）に関する記述などが挙げられる。これらのバリエーションはチャーチやチューリングによるものではなく、後の計算複雑性理論 やデジタル物理学の研究から生まれたものである。このテーゼは 心の哲学 にも影響を与える（下記 参照）。
JB ( 1939 ) は、「有効な計算可能性」の概念について次のように述べている。「明らかに、CC と RC [つまり、真理を決定する有効な方法はないという主張の Church と Rosser の証明] の存在は、「有効」の正確な定義を前提としている。「有効な方法」は、ここでは、各ステップが正確に決定されており、有限のステップで答えを出すことが確実な方法という、かなり特別な意味で使用されている。」[ 18 ] [ 19 ] [ 20 ]
以下では、「実効的に計算可能」とは「直感的に『実効的』な手段によって生成される」という意味であり、「実効的に計算可能」とは「チューリングマシンまたは同等の機械装置によって生成される」という意味である。チャーチの指導の下、1938年にチューリングが提出した博士論文『順序数に基づく論理体系』
† 「計算可能な関数」という表現は、機械で計算可能な関数を意味し、「実質的に計算可能」とは、これらの定義のいずれかに特に関連付けることなく、直感的な概念を指すものとする。[ 21 ]
このテーゼは次のように述べることができる。「すべての有効な計算可能な関数は計算可能な関数である 。 」 [ 22 ] チャーチはまた、「チューリングマシンとして表現できない限り、いかなる計算手順もアルゴリズム とはみなされない」と述べた。[ 23 ]
チューリングはそれを次のように述べた。
「関数の値が何らかの純粋に機械的なプロセスによって求められる場合、その関数は実質的に計算可能である」と述べられている。これを文字通りに解釈し、純粋に機械的なプロセスとは機械によって実行できるプロセスであると理解してもよい。この展開は、計算可能性† と実質的な計算可能性の同一視 につながる。[ † は上記の脚注である。] [ 21 ]
歴史 1930年代の論理学者にとって重要な問題の一つは、デイヴィッド・ヒルベルト とヴィルヘルム・アッカーマン の決定問題 [ 24 ] [ 25 ] [ 26 ] 。「有効計算可能性」の概念は 、（i）公理系における「公理または複数の公理」なのか、（ii）単に2つ以上の命題を「識別」する定義なのか、（iii）自然 現象の観察によって検証される経験的仮説 なのか、（iv）単なる議論のための提案（つまり「テーゼ」）なのか？
この問題の研究過程で、チャーチと彼の学生スティーブン・クリーネは λ定義可能関数 の概念を導入し、数論で頻繁に遭遇するいくつかの大きなクラスの関数がλ定義可能であることを証明することができた。[ 27 ] [ 28 ] を公理化すること を提案した。実際、1935年にクリーネに宛てた手紙の中で、チャーチは次のように報告している。
当時のゲーデルの唯一の考えは、未定義の概念としての有効計算可能性の観点から、この概念の一般的に受け入れられている性質を具体化する一連の公理を述べ、それに基づいて何かを行うことが可能かもしれないということだった。[ 29 ]
しかし、ゲーデルはそれ以上の指針を示さなかった。最終的に、彼はヘルブラントの提案によって修正された自身の再帰を示唆することになるが、それはゲーデルが1934年にニュージャージー州プリンストンで行った講義で詳しく説明したものであった（クリーネとロッサーが そのノートを書き起こした）。しかし、彼は「発見的方法以外では」この2つのアイデアを満足に同一視することはできないと考えていた。[ 30 ]
次に、有効計算可能性の 2 つの概念の等価性を特定し証明する必要があった。 λ 計算と「一般」再帰を備えた Kleene は、Church と J. Barkley Rosser の助けを借りて、2 つの計算が等価であることを示す証明 (1933 年、1935 年) を作成した。 Church はその後、Herbrand–Gödel 再帰の使用を含めるように方法を修正し、Entscheidungsproblem は解決 不可能であることを証明した (1936 年)。つまり、整形式式が ベータ正規形 を持つ[ 31 ]
何年も後、デービスへの手紙（1965年頃）の中で、ゲーデルは「これらの[1934年の]講義の時点では、自分の再帰の概念がすべての可能な再帰を包含しているとは全く確信していなかった」と述べている。[ 32 ] [ 33 ]
自然法則につながる仮説？ ：1936年後半、アラン・チューリングの論文（決定問題が [ 34 ] エミール・ポスト の1936年の論文は既に発表されており、チューリングの研究とは独立していることが確認されていた。[ 35 ]
実際、チャーチらが既に行った研究は、この同一性を作業仮説の段階をはるかに超えて進めている。しかし、この同一性を定義の下に隠してしまうと 、その継続的な検証の必要性が見えなくなってしまう。[ 36 ]
むしろ彼は、「有効計算可能性」という概念を、定義や公理ではなく帰納的推論 によって「自然法則」に導く可能性のある単なる「作業仮説」とみなした。 [ 37 ] [ 38 ]
したがって、ポストは1936年の論文で、1934年から1935年にかけてゲーデルがチャーチに提案した、この命題は公理または公理の集合として表現できるかもしれないという提案も否定していた。[ 29 ]
チューリングは別の定義を追加し、ロッサーは3つすべてを同一視した 。 チューリングの1936年から1937年の論文「計算可能な数について、決定問題 [ 34 ] チューリングマシン 抽象計算モデルとして知られている）の導入により、「実効計算可能性」の別の概念を述べた。1936年から1937年の論文の付録として追加された証明スケッチで、チューリングはλ計算とチューリングマシンによって定義される関数のクラスが一致することを示した。[ 39 ] [ 40 ]
数年後（1939年）、チューリングは、彼以前のチャーチやクリーネと同様に、機械的計算エージェントの形式的定義が正しいと提唱した。 [ 41 ]この 定義 であるべきだと提唱したが、 [ 42 ] テーゼ として提示しなかった。
ロッサー（1939）は、定義としての概念を3つ正式に特定した。
これら3つの定義 はすべて同等なので、どれを使っても構いません。[ 43 ]
クリーネはテーゼI を提唱する：これにより、「テーゼ」の明示的な表現はクリーネに委ねられた。1943年、クリーネは「テーゼI」を提唱した：[ 44 ]
この発見的事実［一般的な再帰関数は実質的に計算可能である］ から、チャーチは次のテーゼを提唱した。チューリングによる計算機の説明にも、同じテーゼが暗黙のうちに含まれている。
テーゼI.すべての実効的に計算可能な関数（実効的に決定可能な述語）は一般的に再帰的である [クリーネの強調] 実質的に計算可能（実質的に決定可能）という用語の厳密な数学的定義がこれまで欠けていたため、本論文を その定義として用いることができる 。
… この命題は仮説の性質を帯びている――これはポストとチャーチが強調した点である。命題とその逆を定義とみなすならば、この仮説は、その定義から展開された数学理論の適用に関する仮説である。そして、我々が示唆したように、この仮説を受け入れるには非常に説得力のある根拠が存在する。
チャーチ＝チューリングのテーゼ ：スティーブン・クリーネは、『メタ数学入門』 の中で、自身の再帰的実現可能性の理論を用いて、ついに「チャーチのテーゼ」と「チューリングのテーゼ」という正式な名称を定めた。これは、それまでチャーチ＝クリーネのラムダ定義可能性の用語を用いていた研究を、ゲーデル＝クリーネの再帰性（部分再帰関数）の用語に切り替えたためである。この移行において、クリーネはゲーデルの一般再帰関数を修正し、EJ・ブラウワーの直観主義における問題の解けなさを証明できるようにした。彼の論理学の大学院教科書では、「チャーチのテーゼ」が紹介され、基本的な数学的結果が実現不可能であることが示された。次に、クリーネは「チューリングのテーゼ」を提示し、エミール・ポストの研究に基づくチューリングマシンの簡略化された導出を用いて、結果が計算不可能であることを示した。両方の命題は「定理XXX」を用いることで同等であることが証明される。
テーゼ I.すべての実効的に計算可能な関数（実効的に決定可能な述語）は一般的に再帰的である 。[ 45 ]
定理 XXX: 次の部分関数のクラスは同外延的である、つまり同じメンバーを持つ: (a) 部分再帰関数、(b) 計算可能な関数 ... [ 46 ]
チューリングのテーゼ：チューリングのテーゼ、すなわち、自然に計算可能と見なされるすべての関数は、彼の定義の下で、つまり彼の機械のいずれかによって計算可能であるというテーゼは、定理 XXX によりチャーチのテーゼと同等である。[ 46 ]
クリーネは最後に、ウィリアム・ブーンからの批判を受けて、アラン・チューリングの論文「相殺を伴う半群における語の問題」の概念を明確にするのに役立つ章で、「チャーチ＝チューリングのテーゼ」という用語を初めて使用した。[ 47 ]
その後の展開 「実効計算可能性」の概念をよりよく理解しようとする試みから、ロビン・ガンディ （チューリングの教え子であり友人）は1980年に機械 計算（チューリングマシンによって実行される人間による計算とは対照的に）を分析した。ガンディはセルオートマトン （コンウェイのライフゲーム を含む）、並列処理、結晶オートマトンに対する好奇心と分析から、 あらゆる機械が満たさなければならないと主張される4つの「原理（または制約）」を提案した[ 48 ] [ 49 ] [ 50 ]
1990年代後半、ウィルフリード・ジークは チューリングとガンディの「実効計算可能性」の概念を分析し、「非形式的な概念を明確化し、その一般的な特徴を公理的に定式化し、公理的枠組みを調査する」ことを意図した。[ 51 ] ジークは1997年と2002年の著作で、コンピュータ （「機械的に進む人間の計算エージェント」）の振る舞いに関する一連の制約を提示している。これらの制約は以下のように要約される。
（B.1）（制限）コンピュータが即座に認識できる記号構成の数には固定された制限がある。 （B.2）（有界性）コンピュータがとりうる内部状態の数には固定された上限がある。 (L.1) (局所性) コンピュータは、観測された記号構成の要素のみを変更できます。 （L.2）（局所性）コンピュータは、ある記号構成から別の記号構成に注意を移すことができますが、新たに観測される構成は、直前に観測された構成から一定の距離内になければなりません。 「（D）（決定性）すぐに認識できる（サブ）構成によって、次の計算ステップ（およびid［瞬間的な記述］）が一意に決定される」；別の言い方をすれば、「コンピュータの内部状態と観測された構成によって、次の計算ステップと次の内部状態が一意に決定される」[ 52 ] この問題は学術界で活発に議論されている。[ 53 ] [ 54 ]
定義としての論文 このテーゼは、単なる普通の数学的定義と見なすことができる。この主題に関するゲーデルのコメントは、この見解を示唆している。例えば、「機械的計算可能性の正しい定義は、チューリングによって疑いの余地なく確立された」[ 55 ] られ て おり、 チューリングの計算可能性の定義は、連続関数 のイプシロンデルタ定義よりも正しい可能性が低いわけではないとも主張されている。
計算可能性理論の証明では、厳密な形式的証明で必要となる（しばしば非常に長い）詳細を避けつつ、関数の計算可能性を確立するために、非公式な方法でチャーチ・チューリングのテーゼがしばしば用いられる。[ 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 ] ：
ユニバーサルチューリングマシンは、 任意のチューリングマシンをシミュレートする際に対数的な速度低下しか受けないことが証明されている。[ 62 ]
チャーチ・チューリングのテーゼの変形は、任意の「妥当な」計算モデルを効率的にシミュレートできるかどうかを扱っています。これは実現可能性テーゼ と呼ばれ、[ 63 ] （古典的な ）複雑性理論チャーチ・チューリングのテーゼ 、または拡張チャーチ・チューリングのテーゼ としても知られていますが、チャーチやチューリングによるものではなく、複雑性理論 の発展の中で徐々に実現されたものです。それは次のように述べています。[ 64 ] 確率的チューリングマシンは、 あらゆる現実的な計算モデルを効率的にシミュレートできる。」ここで「効率的に」という言葉は、多項式時間での還元 までを意味します。このテーゼは、もともとイーサン・バーンスタインとウメシュ・ヴァジラニ（1997）によって 計算複雑性理論チャーチ・チューリングのテーゼ と呼ばれていました。複雑性理論チャーチ・チューリングのテーゼは、すべての「妥当な」計算モデルが、多項式時間で計算できる同じクラスの問題を生み出すと仮定しています。確率的多項式時間 ( BPP ) が決定論的多項式時間 ( P ) に等しいという予想を仮定すると、複雑性理論のチャーチ・チューリングのテーゼでは「確率的」という言葉は省略可能である。同様のテーゼである不変性 テーゼは、Cees F. Slot と Peter van Emde Boas によって提唱された。それは、「 『 妥当な』マシンは、時間的に多項式で制限されたオーバーヘッドと空間的に定数倍のオーバーヘッド内で互いにシミュレートできる」と述べている。[ 65 ] STOC '84 の論文で発表されたもので、チューリングマシン上での ランダムアクセスマシン のシミュレーションにおいて、多項式時間オーバーヘッドと定数空間オーバーヘッドを同時に 達成できることを示した最初の論文であった。[ 66 ]
BQP が BPP の厳密な上位集合であることが示されれば、複雑性理論のチャーチ・チューリングのテーゼは無効になる。言い換えれば、効率的な確率的アルゴリズム が存在しないタスクを実行する効率的な量子アルゴリズム が存在することになる。しかし、量子コンピュータは常にチューリングマシンでシミュレートできるため、これは元のチャーチ・チューリングのテーゼを無効にするものではないが、効率上の理由から古典的な複雑性理論のチャーチ・チューリングのテーゼを無効にすることになる。したがって、量子複雑性理論のチャーチ・チューリングのテーゼは 次のように述べている。[ 64 ] 量子チューリングマシンは、 あらゆる現実的な計算モデルを効率的にシミュレートできる。」
ユージン・エーベルバッハとピーター・ウェグナーは、チャーチ＝チューリングのテーゼが時として広範に解釈されすぎていると主張し、「チューリングマシンはアルゴリズムの振る舞いを表現しているが、アルゴリズムが計算可能なものを正確に捉えているというより広範な主張は無効である」と述べている。[ 67 ] スーパーチューリング計算 と呼んでいると主張している。
計算不可能な関数 計算不可能な関数を形式的に定義することは可能である。そのような関数のよく知られた例として、ビジービーバー 関数がある。この関数は入力nを受け取り、入力なしで実行した場合に、 n 個の状態を持つチューリングマシンが停止するまでに出力できる最大の記号数を返す。ビジービーバー関数の上限を求めることは、停止問題 を解くことと同等であり、停止問題はチューリングマシンでは解けないことが知られている。ビジービーバー関数はチューリングマシンでは計算できないため、チャーチ＝チューリングのテーゼによれば、この関数はいかなる方法でも効果的に計算することはできない。
いくつかの計算モデルでは、（チャーチ＝チューリングの）計算不可能な関数を計算することが可能です。これらはハイパーコンピュータ として知られています。
マーク・バーギンは、帰納的チューリングマシンなどの超再帰的アルゴリズムが チャーチ＝チューリングのテーゼを否定すると主張している。[ 75 ]
注記 ↑ 計算可能性テーゼ 、 [ 1 ] チューリング ・チャーチテーゼ 、 [ 2 ] チャーチ ・チューリング予想 、 チャーチのテーゼ 、 チャーチ予想 、 チューリングのテーゼ としても知られています。
参考文献 ↑ Soare, Robert I. (2009-09-01). "チューリングオラクルマシン、オンラインコンピューティング、および計算可能性理論における3つの変位" . Annals of Pure and Applied Logic . Computation and Logic in the Real World: CiE 2007. 160 (3): 368– 399. doi : 10.1016/j.apal.2009.01.008 . ISSN 0168-0072 . ↑ Conrad, Michael (1985 年 5 月). 「分子コンピュータの設計原理について」. Communications of the ACM . 28 (5): 464–480 . doi : 10.1145/3532.3533 . ↑ シュタイナート＝スレルケルド、シェーン。 「ラムダ計算」 。 インターネット哲学百科事典。 2026年2月24日 取得 。 ↑ Church, Alonzo (1935 年 5 月) 「初等整数論の解決不可能な問題。予備報告」 (PDF) . アメリカ数学会報 . 41 (5): 332– 333 . 2026 年 2 月 24 日 に取得. ↑ Church, Alonzo (1935 年 7 月) 「初等整数論の解決不可能な問題 (予備報告)」 (PDF) . アメリカ数学会報 . 41 (7): 453 . 2026 年 2 月 24 日 に取得. ↑ Church, Alonzo (1936 年 4 月). 「初等整数論の解決不可能な問題」 . American Journal of Mathematics . 58 (2): 345–363 . doi : 10.2307/2371045 . 2026 年 2 月 24 日 取得. ↑ チャーチの論文の要旨は、1935 年 3 月 22 日に米国数学会報に受理され、 [ 4 ] [ 5 ] [ 6 ] ↑ アロンゾ・チャーチ文書に収められた マックス・ニューマン とチャーチ の間の書簡 ↑ チューリング、アラン（2004）。 『チューリングの真髄 ：コンピューティング、論理学、哲学、人工知能、人工生命に関する重要な著作、そしてエニグマの秘密』 （PDF） 。オックスフォード：クラレンドン・プレス。44 ページ 。ISBN 9780198250791 2021年12月6日 に取得 。↑ Turing, AM (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem" . Proceedings of the London Mathematical Society . s2-42 (1): 230– 265. doi : 10.1112/plms/s2-42.1.230 . 2026年2月24日 取得。 1 2 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 . ↑ 自身の研究成果の執筆にかなりの進展を見せていたチューリングは、チャーチの論文が発表されて間もなくその事実を知り、落胆した。 [ 8 ] [ 9 ] ロンドン数学会紀要に受理され、同年11月12日に読まれ、シリーズ2、第42巻（1936～1937年）に掲載された。 [ 10 ] [ 11 ] : ↑ 教会 1936a ↑ クリーネ 1936 ↑ チューリング 1937a ↑ クリーネ 1936 ↑ チューリング 1937b 。証明の概要は153ページにあります 。λ -定義可能 {\displaystyle \lambda {\mbox{-definable}}} ⟹ t r 私 v {\displaystyle {\stackrel {triv}{\implies }}} λ - K -定義可能 {\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}} ⟹ 160 {\displaystyle {\stackrel {160}{\implies }}} チューリング計算可能 {\displaystyle {\mbox{チューリング計算可能}}} ⟹ 161 {\displaystyle {\stackrel {161}{\implies }}} μ -再帰的 {\displaystyle \mu {\mbox{-recursive}}} ⟹ K l e e n e {\displaystyle {\stackrel {Kleene}{\implies }}} [ 16 ] λ -定義可能 {\displaystyle \lambda {\mbox{-definable}}} ↑ Rosser 1939 in Davis 1965 :225 。↑ 「効果的な」。 メリアム・ウェブスター新大学辞典 （第9 版）。 ↑ 「effective」 も参照。メリアム・ウェブスターオンライン辞書 （第11 版） 。 2014年7月26日 取得 。 1 2 Turing, AM (1938). 順序数に基づく論理体系 (PDF) (PhD). プリンストン大学. p. 8. 2012年10月23日に オリジナル (PDF) からアーカイブ済み 。 2012年6月23日 に取得。 ↑ ガンディ（1980年 ：123） は次のように述べている。「実質的に計算可能なものは計算可能である」。彼はこれを「チャーチのテーゼ」と呼んでいる。↑ コープランド、B. ジャック (2024)、 「チャーチ＝チューリングのテーゼ」 、ザルタ、エドワード N.、ノーデルマン、ウリ (編)、 『スタンフォード哲学百科事典 』 （2024 年冬 版）、形而上学研究室、スタンフォード大学、 2025 年 6 月 11 日 取得 ↑ ヒルベルト、デイヴィッド;アッカーマン、ヴィルヘルム (1972) [第 1 版] 1928年]。 Grundzüge der theoretischen Logik [ 理論論理の基礎 ] (ドイツ語) (第 6 版)。ドイツ、ベルリン：シュプリンガー。 ISBN 3-540-05843-5 。『数学論理学の原理』 （1950年）として出版。米国ロードアイランド州プロビデンス：AMSチェルシー出版。↑ デイビスの解説は、チャーチ 1936より前のもので、 デイビス 1965 :88 ↑ アダム・オルシェフスキー他編著 『チャーチのテーゼ70年後』 （2006年）のレビューの中で、ピーター・スミス はムラフスキーとウォレンスキーの論文を批判し、チャーチ＝チューリングのテーゼの地位について4つの「線」を示唆している。(1) 経験的仮説、(2) 公理または定理、(3) 定義、(4) 説明。しかし、スミスは(4)は(3)と区別できないと述べている。スミス、ピーター（2007年7月11日）。 「チャーチのテーゼ70年後」 （PDF） 。Logic Matters 。 ↑ Church 1936a An Unsolvable Problem of Elementary Number Theory 、 Davis 1965 :89 の 脚注 3。 ↑ ドーソン 1997 :99 。1 2 Sieg 1997 :160 .↑ Sieg 1997 :160 、チャーチがクリーネに宛てた1935年の手紙からの引用、 Gödel 1965 の脚注3、 Davis 1965 :44 。↑ Church 1936 Davis 1965 :105ff. ↑ デービスによる ゲーデル1965 以前の解説、デービス1965 :40 。 ↑ ゲーデルがチューリングの機械を計算モデルとして採用したことに関する詳細な議論については、シャグリール、オロン （2006年6月15日） 「 ゲーデルのチューリングの計算可能性論」 （PDF） を 参照。 チャーチの論文70年後。デ・グリュイター。393 ～ 419 ページ。doi : 10.1515 /9783110325461.393。ISBN 978-3-11-032494-5 2015年12月17日にオリジナル（PDF） からアーカイブされました。2016年2月8日 に取得 。 1 2 チューリング 1937a 。↑ 編集者による脚注「Post 1936 Finite Combinatory Process. Formulation I. at Davis 1965 :289 」。 ↑ 1936年の投稿、 Davis 1965 :291、脚注8。 ↑ デイビス 1965 :291 の Post 1936。 ↑ ジーク 1997 :171 および 176–177 。↑ チューリング 1936–1937、デイビス 1965 :263ff。 ↑ チャーチ 1937 。↑ チューリング 1939年、デイビス:160。 ↑ Church 1934 in Davis 1965 :100 、Turing 1939 in Davis 1965 :160 も参照。 ↑ Rosser 1939 in Davis 1965 :226 (強調追加)。↑ クリーネ 1943 、デイビス 1965:274 の p. 60 ( 脚注 省略 )。 ↑ クリーネ 1952 :300。1 2 クリーネ 1952 :376.↑ クリーネ 1952 :382, 536 ↑ ガンディ 1980 :123ff. ↑ ガンディ 1980 :135 ↑ ガンディ 1980 :126 ↑ Sieg 1998–1999 in Sieg, Sommer & Talcott 2002 :390ff。 ;ジーク 1997 :154ff とも ↑ 脚注で、ジークはポストの1936年の(B)を(B.1)と(B.2)に、(L)を(L.1)と(L.2)に分割し、(D)を異なる方法で説明している。彼が提案したガンディマシン に関して、彼は後にLC.1、LC.2、GA.1、GA.2を追加した。これらは複雑である。ジーク、ソマー、 タルコット2002 :390ffのジーク1998-1999を参照。 ↑ 論文集はOlszewski、Woleński 、 Janusz (2006) に掲載されています。また、この論文集のレビューは、 Smith、Peter (2007-07-11) 「70年後のチャーチのテーゼ」 (PDF) にあります。 ↑ 参照： Hodges, Andrew (2005). "Did Church and Turing Have a Thesis about Machines?" (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）の翻訳は『決定不能なもの 』83ページに掲載されているが、クリーネ（1952）321ページの翻訳では「reckonable」という語が使われている点で異なっている。 ↑ Horsten、 Olszewski、Woleński 、 Janusz 2006 :256 。 ↑ ギャベイ 2001 :284 ↑ Piccinini, Gualtiero (2007年1月) 「計算主義、チャーチ＝チューリングのテーゼ、そしてチャーチ＝チューリングの誤謬」 . Synthese . 154 (1): 97–120 . CiteSeerX 10.1.1.360.9796 . doi : 10.1007/s11229-005-0194-z . S2CID 494161. 2008年4月24日にオリジナルから アーカイブ （PDF） 。 ↑ Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach . Cambridge University Press . ISBN 978-0-521-42426-4 。↑ 「公式問題説明」 （PDF） 。 2005年11月24日に オリジナル （PDF） からアーカイブされました。 1 2 ケイ、フィリップ；ラフラム、レイモンド；モスカ、ミケーレ（2007）。 量子 コンピューティング入門 。オックスフォード大学出版局。5-6 頁 。ISBN 978-0-19-857049-3 。↑ van Emde Boas, Peter (1990). "Machine Models and Simulations". Handbook of Theoretical Computer Science 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 . ↑ コープランド、B. ジャック (2017-11-10). 「チャーチ＝チューリングのテーゼ」 . ザルタ、エドワード N. (編) 『スタンフォード哲学百科事典』 . ISSN 1095-5054 . OCLC 429049174 . ↑ 原著論文を探すのに適した資料としては、David J. Chalmers 編 (2002). Philosophy of Mind: Classical and Contemporary Readings . New York: Oxford University Press. ISBN を参照のこと。 978-0-19-514581-6 OCLC 610918145 ↑ コープランド、B. ジャック (2004)。「計算」。 フロリディ、ルチアーノ (編) 『ブラックウェル式コンピューティングと情報哲学ガイド』所収 。ワイリー・ブラックウェル。15 ページ 。ISBN 978-0-631-22919-3 。↑ 参照：ロジャー・ペンローズ （1990）「アルゴリズムとチューリングマシン」『皇帝の新しい心：コンピュータ 、 心、そして物理法則について 』オックスフォード：オックスフォード大学出版局、 47-49 頁。ISBN 978-0-19-851973-7 OCLC 456785846。 ↑ また、「数学的洞察の非アルゴリズム的性質」に関する記述については、ロジャー・ペンローズ （1990）「心の物理学はどこにあるのか？」 『皇帝の新しい心：コンピュータ、心、そして物理法則について』 オックスフォード：オックスフォード大学出版局、 416～ 418頁、 ISBNを参照。 978-0-19-851973-7 OCLC 456785846。 ↑ Piergiorgio Odifreddi (1989). Classical Recursion Theory . Studies in Logic and the Foundations of Mathematics. Vol. 125. Amsterdam, Netherlands: North Holland. ↑ バーギン、マーク（2005）。 スーパー再帰アルゴリズム 。コンピュータサイエンスモノグラフ。ニューヨーク：スプリンガー 。ISBN 978-0-387-95569-8 . OCLC 990755791 .
情報源 バーワイズ、ジョン ；ケイスラー、HJ ；クーネン、ケネス 編（1980）。クリーネ・シンポジウム 。アムステルダム：ノースホランド出版。ISBN 978-0-444-85345-5 。Ben-Amram, AM (2005). "The Church-Turing Thesis and its Look-Alikes" . SIGACT News 36 (3): 113–116 . CiteSeerX 10.1.1.74.7308 . doi : 10.1145/1086649.1086651 . S2CID 13566703. 2017年7月6日にオリジナル(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) 。 バーギン、マーク（2005）。「超再帰アルゴリズム」。コンピュータサイエンスモノグラフ 。シュプリンガー。ISBN 978-0-387-95569-8 。 チャーチ、アロンゾ（1932）。「論理の基礎のため の公準の集合」。Annals of Mathematics。33 （2 ）：346–366。doi ：10.2307 /1968337。JSTOR 1968337 。 チャーチ、アロンゾ（1936年4月a）。 「初等整数論の解決 不可能な問題」（PDF） 。アメリカ数学ジャーナル 。58 （2）：345–363。doi ：10.2307/2371045。JSTOR 2371045。S2CID 14181275。 2020年2 月 27日にオリジナル（PDF） からアーカイブ済み。 チャーチ、アロンゾ（ 1936 年 6月b ）。「決定問題に関する覚書」。記号論理学ジャーナル 。1 （ 1）：40–41。doi ：10.2307 / 2269326。JSTOR 2269326。S2CID 42323521。 チャーチ、アロンゾ（1937年3月） 。「書評：AMチューリング著『計算可能な数について、決定問題への応用』」。記号論理学ジャーナル 。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 . Davis, Martin 編 (1965). 『決定不能性：決定不能な命題、解決不能な問題、計算可能な関数に関する基礎論文』 ドーソン、ジョン・W・ジュニア（1997）。論理的ジレンマ：クルト・ゲーデルの生涯と業績 。ウェルズリー、マサチューセッツ州、米国：AKピーターズ 。 Eberbach, E.; Wegner, P. (2003年10月). "Beyond Turing Machines" (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 版）。 Gandy, Robin (1980). 「チャーチのテーゼとメカニズムの原理」。HJ Barwise、HJ Keisler、K. Kunen (編) 『クリーネ・シンポジウム』 所収。North-Holland Publishing Company、pp. 123–148 。 ガンディ、ロビン（1994）。ヘルケン、ロルフ（編）。普遍的なチューリング マシン: 半世紀にわたる調査 。ニューヨーク: ウィーン・シュプリンガー – フェルラーク。 51ページ以降 。ISBN 978-3-211-82637-9 。 ゲーデル、クルト (1936)。 「Über die Lāange von Beweisen」[ 証明の長さについて] 。Ergenbnisse Eyenes Mathematishen Kolloquiums (ドイツ語) (7)。身長：23～ 24。 クリーネ（1952） によって引用されている。Gurevich, Yuri (1988年6月). 「コルモゴロフマシンと関連問題について」.欧州理論計算機科学協会紀要 (35): 71–82 .Gurevich, Yuri (2000年7月) 「逐次抽象状態機械は逐次アルゴリズムを捉える」(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年2月5日)「第17章：チャーチ、チューリング、タルスキ、その他」『ゲーデル、エッシャー、バッハ：永遠の黄金の鎖』 （20周年記念 版）ベーシックブックス 、559-585頁 。ISBN 0-465-02656-7 。Kleene, Stephen Cole (1935 年 1 月). 「形式論理における正の整数の理論」 . American Journal of Mathematics . 57 (1): 153–173 & 219–244. doi : 10.2307/2372027 . JSTOR 2372027 . Kleene, Stephen Cole (1936). "ラムダ定義可能性と再帰性" . Duke Mathematical Journal 2 (2): 340– 353. doi : 10.1215/s0012-7094-36-00227-2 . Kleene, Stephen Cole (1943). 「再帰的述語と量化子」 .アメリカ数学会紀要 . 53 (1): 41– 73. doi : 10.2307/1990131 . JSTOR 1990131 . 『決定不能』 。クリーネは「一般再帰」の定義を洗練し、第12章「アルゴリズム理論」で「テーゼI」（ 274ページ）を提唱した。彼は後にこのテーゼを繰り返し（クリーネ1952 :300）、それを「チャーチのテーゼ」（ クリーネ1952 :317）（つまりチャーチのテーゼ ）と名付けた。クリーネ、スティーブン・コール（1952）。メタ数学入門 。ノースホランド。OCLC 523942 。 クヌース、ドナルド （1973）。コンピュータプログラミングの技法 。第 1巻／基本アルゴリズム（第2 版）。アディソン・ウェスリー。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メンテナンス: 場所の発行元が見つかりません (リンク)Markov, AA (1960) [1954]. 「アルゴリズムの理論」.アメリカ数学会翻訳 . 2 (15): 1– 14.Olszewski, Adam; Woleński, Jan; Janusz, Robert 編 (2006). Church's Thesis After 70 Years . Frankfurt: Ontos. ISBN 978-3-938793-09-1 OCLC 909679288 Pour-El, MB ; Richards, JI (1989).解析と物理学における計算可能性 Springer Verlag .Rosser, JB ( 1939 ). 「ゲーデルの定理とチャーチの定理 の 証明に関する非公式な解説」 『記号論理学ジャーナル 』4 (2): 53–60 . doi : 10.2307/ 2269059.JSTOR2269059.S2CID39499392 . Sieg, Wilfried (1997年6月)「再帰的ステップごとのステップ：チャーチによる有効計算可能性の分析」『記号論理学紀要 』3 (2): 154–180 . doi : 10.2307/ 421012.JSTOR 421012 . ジーク、ウィルフリード；ゾンマー、リチャード；タルコット、キャロリン編（2002）。数学の基礎に関する考察：ソロモン・フェファーマン教授への献呈論文集 。論理学講義録。第 15巻。AK Peters, Ltd. ISBN 978-1-56881-169-7 。 シロプロス、アポストロス（2008）。ハイパーコンピューティング：チャーチ・チューリングの壁を越えるコンピューティング 。シュプリンガー。ISBN 978-0-387-30886-9 。 Turing, AM (1937a) [1936年11月に学会で発表]、「計算可能な数について、決定問題への応用」（PDF） 、ロンドン数学会紀要 、2巻、第 42巻、230～ 265ページ、Bibcode ：1937PLMS...42..230T、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 。 デイビス 1965 ：115頁以降）チューリング、アラン・マティソン（1937年12月b）。「計算可能性と λ定義可能性」（PDF） 。記号論理学ジャーナル 。2 （ 4）：153–163。doi ：10.2307/2268280。JSTOR 2268280。S2CID 2317046。 2020年8月9日に オリジナル（PDF） からアーカイブ済み。 
