教会史―チューリングのテーゼ

チャーチ＝チューリングのテーゼ（以下「テーゼ」）の歴史は、 値が実質的に計算可能な関数、あるいはより現代的な言い方をすれば、値がアルゴリズム的に計算可能な関数の性質に関する研究の発展の歴史と深く関わっています。これは現代の数学理論とコンピュータ科学において重要なテーマであり、特にアロンゾ・チャーチとアラン・チューリングの研究と密接に関連しています。

「計算」と「再帰」の意味をめぐる議論と発見は、長年にわたり論争の的となってきた。本稿では、1889年のペアノの公理から、近年の「公理」の意味に関する議論に至るまで、その議論と発見の詳細を解説する。

1889年、ジュゼッペ・ペアノはデデキントの研究に基づき、新しい方法で提示された算術の原理を発表した。ソアレは「原始再帰」の起源は形式的にはペアノの公理から始まったと提唱しているが、

「19世紀よりずっと前から、数学者たちは帰納法によって関数を定義する原理を用いていた。デデキントは1888年に、受け入れられた公理を用いて、そのような定義が一意の関数を定義することを証明し、それを関数m+n、mxn、m ⁿの定義に適用した。デデキントのこの研究に基づいて、ペアノは1889年と1891年に、正の整数に関するよく知られた5つの公理を書いた。ペアノは、5番目の公理である数学的帰納法の補足として、帰納法による定義を用いた。これは（ペーター1934年とクリーネ1936年以来）原始的再帰と呼ばれている…」^{[ 1 ]}

実際、ペアノの公理は9つあり、公理9は再帰/帰納法の公理であることに注意してください。 ^{[ 2 ]}

「その後、9つの公理は5つに減らされました。なぜなら、同一性を扱う公理2、3、4、5は基礎論理に属するからです。これにより、5つの公理が残り、これらは広く「ペアノ公理」として知られるようになりました。ペアノは（1891b、p.93）彼の公理がデデキントに由来することを認めています…」^{[ 3 ]}

1900年にパリで開催された国際数学者会議（ICM）で、著名な数学者ダフィット・ヒルベルトは、現在ヒルベルト問題として知られる一連の問題を提起し、20世紀の数学者たちの道を照らした。ヒルベルトの第2問題と第10問題は、「決定問題」 （ Entscheidungsproblem ）を導入した。第2問題では、「算術」が「無矛盾」であることの証明を求めた。クルト・ゲーデルは1931年に、彼が「P」（現在ではペアノ算術と呼ばれる）と呼んだものの中に「決定不可能な文（命題）が存在する」ことを証明した。^{[ 4 ]}このため、「Pが無矛盾である限り、Pの無矛盾性はPの中で証明不可能である」。^{[ 5 ]}ゲーデルの証明はアロンゾ・チャーチとアラン・チューリングが決定問題を解決するため に必要なツールを示したが、ゲーデル自身はそれに答えることはなかった。

決定問題という概念が実際に現れたのは、ヒルベルトの第10問題においてである。問題の核心は、「関数が『実効的に計算可能』であるとはどういう意味か」という問いであった。その答えは概ね、「関数が機械的な手順（プロセス、方法）によって計算される場合」となるだろう。今日では容易に述べられるこの問い（と答え）は、正確に定式化されるまでに30年近くも議論の的となった。

ヒルベルトによる問題10の元の記述は、次のように始まる。

「 10．ディオファントス方程式の可解性の判定。任意の数の未知量と有理整数係数を持つディオファントス方程式が与えられた場合、有限回の演算で、その方程式が有理整数で解けるかどうかを判定できる手順を考案する。^{[ 6 ]}」

1922年までに、ディオファントス方程式に適用される決定問題という具体的な問題は、あらゆる数学式に対する「決定方法」に関するより一般的な問題へと発展しました。マーティン・デイビスは次のように説明しています。 （1）公理の集合と（2）一階述語論理で書かれた論理的結論、つまりデイビスが「フレーゲの演繹規則」（またはブール論理の現代版）と呼ぶもので書かれた論理的結論からなる「計算手順」が与えられたとします。ゲーデルの博士論文^{[ 7 ]}は、フレーゲの規則が「…すべての有効な式は証明可能である」という意味で完全であることを証明しました。 ^{[ 8 ]} この心強い事実を踏まえると、結論が前提から導き出せるかどうかを教えてくれる一般化された「計算手順」が存在するでしょうか。デイビスはこのような計算手順を「アルゴリズム」と呼んでいます。決定問題もまたアルゴリズムです。 「原則として、[決定問題]のアルゴリズムは、人間の演繹的推論をすべて総当たり計算に還元するだろう。」^{[ 9 ]}

言い換えれば、あらゆる数式が「真」であるかどうかを判断できる「アルゴリズム」（つまり、常に「真」か「偽」かを正しく判定するアルゴリズム）は存在するのだろうか？

「…ヒルベルトにとって、この問題、すなわち決定問題の解決によって、原理的にはすべての数学的問題を純粋に機械的な方法で解決できるはずであることは明らかだった。したがって、解決不可能な問題がそもそも存在するならば、ヒルベルトが正しければ、決定問題自体も解決不可能であるはずだ。」^{[ 10 ]}

確かに、私たちの判断問題アルゴリズム自体はどうでしょうか？有限のステップ数で、アルゴリズム自体が「成功」かつ「真実」であるかどうかを判断できるでしょうか（つまり、無限の「循環」や「ループ」に陥ることなく、自身の動作や結果について「真実」または「虚偽」という判断を正しく下せるでしょうか）？

1928年のボローニャで開催された会議で、ヒルベルトはこの問題を非常に慎重に3つの部分に絞り込んだ。以下はスティーブン・ホーキングによる要約である。

• 「1. すべての真の数学的命題は証明可能であることを証明すること、すなわち、数学の完全性を証明すること。」
• 「2. 真の数学的命題のみが証明できること、すなわち数学の一貫性を証明するために、
• 「3. 数学の決定可能性、すなわち、任意の数学的命題の真偽を判定する決定手続きの存在を証明すること。」 ^{[ 11 ]}

ガブリエル・スーダン（1927年）とヴィルヘルム・アッカーマン（1928年）は、原始再帰ではない再帰関数を示した。

「原始的な再帰に還元できない再帰は存在するのか。特に、原始的な再帰ではない関数を定義するために再帰を使用することは可能か。」

「この問題は、1926年にヒルベルトが連続体問題について立てた予想から生じ、1928年にアッカーマンによって（原始再帰的ではない再帰が存在するという）答えが出されました。」^{[ 12 ]}

その後、クリーネ^{[ 13 ]}は、ローザ・ペーター（1935）がアッカーマンの例（「ヒルベルト＝ベルネイス1934も参照」）とラファエル・ロビンソン（1948）を簡略化したことを指摘している。ペーターはカントールの対角線論法を用いた別の例（1935）を示した。ペーター（1950）とアッカーマン（1940）は「超限再帰」も示しており、このことからクリーネは疑問を抱いた。

「…我々は、いかなる「再帰」の概念、あるいはすべての「再帰関数」のクラスを、何らかの正確な方法で特徴づけることができるかどうか。」^{[ 14 ]}

クリーネは^{[ 15 ]}、すべての「再帰」には(i)彼が§54「原始再帰関数の形式的計算」で提示した形式的分析と、(ii)数学的帰納法の使用が含まれると結論付けている。彼はすぐに、ゲーデル＝ヘルブランドの定義が実際に「すべての再帰関数を特徴づけている」と述べている（1934年の以下の引用を参照）。

1930年、数学者たちは数学会議とヒルベルトの退職記念行事のために集まった。幸運なことに、

「まさにその会議で、若いチェコの数学者クルト・ゲーデルが、ヒルベルトの3つの答えすべてがYESであるという意見に深刻な打撃を与える結果を発表した。」 ^{[ 16 ]}

彼は、1928年のヒルベルトの3つの質問のうち最初の2つに対する答えは「いいえ」だと発表した。

その後、1931年にゲーデルは有名な論文「プリンキピア・マテマティカの形式的に決定不可能な命題と関連体系について I」を発表した。マーティン・デイヴィスはこの論文の序文で次のような注意を述べている。

「読者は、この論文ではゲーデルが再帰関数と呼んでいるものが、原始再帰関数 と呼ばれていることに注意すべきである。（この改訂された用語はクリーネ^{[ 17 ]}によって導入された。）」^{[ 18 ]}

クリーネ（1952）の言葉を引用すると、「すべての「再帰関数」の特徴付けは、ヘルブラントの提案に基づいて、ゲーデル（1934）による「一般再帰関数」の定義によって達成された」（クリーネ 1952:274）。ゲーデルは、ニュージャージー州プリンストンの高等研究所（IAS）で一連の講義を行った。マーティン・デイビス^{[ 19 ]}が書いた序文の中で、デイビスは次のように述べている。

「ゲーデル博士は手紙の中で、これらの講義の時点では、自身の再帰の概念がすべての可能な再帰を包含しているとは全く確信していなかったと述べている…」^{[ 20 ]}

ドーソンは、これらの講義は「不完全性定理が形式化の特殊性に何らかの形で依存している」という懸念を明確にするためのものであったと述べている: ^{[ 21 ]}

ゲーデルは1934年の論文の最終節でアッカーマンの例を挙げ、そこで定義した「一般再帰関数」の概念を動機づける方法として用いた。しかし、それ以前の脚注3では、すでに（「発見的原理」として）すべての有限計算可能な関数は、そのようなより一般的な種類の再帰によって得られると推測していた。

「この予想はその後、多くの議論を巻き起こしました。特に、マーティン・デイビスがゲーデルの1934年の講義を出版しようとしたとき（デイビス 1965:41ff）、彼はそれをチャーチのテーゼの変形とみなしました。しかし、デイビスへの手紙の中で… ^{[ 22 ]}ゲーデルは、その講義の時点では、再帰の概念が「すべての可能な再帰」を含むと「全く確信していなかった」ため、それは「真実ではない」と断言しました。むしろ、彼は「そこで述べられた予想は、『有限（計算）手順』と『再帰手順』の等価性のみを指している」と述べました。この問題を明確にするために、ゲーデルは講義に追記を加え^{[ 23 ]} 、直感的に計算可能な関数が一般的な再帰関数と一致すると最終的に確信したのはアラン・チューリングの研究（チューリング 1937 ）であったことを示しました。

「ゲーデルが、一般的な再帰性またはλ定義可能性のいずれも、非形式的な有効計算可能性の概念を適切に特徴付けるものとは考えなかったことは、複数の著者によって詳細に検討されている[脚注248: 特にDavis 1982; Gandy 1980および1988を参照]。ジーク（1994）によれば、実際にはゲーデルとチャーチの形式主義は、アラン・チューリングの分析ほど明快でも本質的に説得力があるわけでもなかったという点で意見が一致しており、ヴィルフリート・ジークは、「異なる概念の融合」（チャーチ、ゲーデル、ポスト、アラン・チューリングが提案した体系がすべて同じ拡張を持つことが判明したという事実）によってチャーチのテーゼを支持する証拠は、一般的に考えられているほど説得力がないと主張している。したがって、ゲーデルの生来の慎重さとは別に、彼の懐疑主義には十分な理由があった。では、彼は一般再帰性の概念を通して何を達成しようとしていたのだろうか？…

「むしろ、ゲーデルはヘルブラントの考えを修正することによって[一般再帰関数のクラスの]定義を得たのであり、ヴィルフリート・ジークは、1934年の論文[講義ノート]の最終節におけるゲーデルの真の目的は、 「方程式を導出するための機械的な規則」を規定することによって、 「再帰関数を[ヘルブラントの]認識論的に制限された証明の概念から切り離すこと」であったと主張している。ジークによれば、ゲーデルの「一般」再帰性の概念でより一般的だったのは、ヘルブラントが有限の手段によって再帰的であることが証明できる関数のみを特徴づけようとしていたことだった[250]。」^{[ 24 ]}

クリーネとロッサーは、ゲーデルの1934年のプリンストン大学での講義を​​書き起こした。クリーネは論文「自然数の一般再帰関数」^{[ 25 ]}の中で次のように述べている。

「自然数の一般的な再帰関数の定義はヘルブラントがゲーデルに提案し、ゲーデルは1934年にプリンストンで行った一連の講義で重要な修正を加えてそれを使用しました... ^{[ 26 ]}

「ゲーデルの意味での再帰関数（関係）は、原始再帰関数（関係）と呼ばれることになる。^{」[ 27 ]}

チャーチの論文「初等整数論の解決不可能な問題」（1936年）は、決定問題がλ計算とゲーデル＝ヘルブラントの一般再帰の範囲内で決定不可能であることを証明した。さらにチャーチは、 λ計算で定義された関数が一般再帰で定義された関数と同一であることを証明したクリーネの2つの定理を引用している。

定理XVI．正の整数のすべての再帰関数はλ定義可能である^。16

「定理XVII．正の整数のλ定義可能な関数はすべて再帰的である^。17

「¹⁶ ...。この形では、最初にクリーネによって得られた...。

「¹⁷この結果は、筆者とSCクリーネによってほぼ同時期に独立して得られたものです。

この論文は、非常に長い脚注3で始まっている。別の脚注9も興味深い。マーティン・デイビスは、「この論文は、有限アルゴリズムで計算できる関数はまさに再帰関数であるという明示的な記述（チャーチのテーゼとして知られる）と、明示的な解けない問題を与えることができるという結果において、主に重要である」と述べている。^{[ 28 ]}

「³後述するように、有効計算可能性のこの定義は、2つの同値な形式のいずれかで述べることができる。(1) ... λ定義可能 ... 2) ... 再帰的 ... 。λ定義可能性の概念は、筆者とSCクリーネの共同によるものであり、筆者は『Annals of Mathematics』第34巻（1933年）、863ページで、クリーネは『American Journal of Mathematics』第57巻（1935年）、219ページで、この概念への段階的な進展を遂げた。以下の§4の意味での再帰性の概念は、ジャック・エルブランとクルト・ゲーデルの共同によるものであり、そこで説明されている。そして、2つの概念の同値性の証明は、主にクリーネによるものであるが、筆者とJBロッサーにも一部貢献している。これらの概念を有効計算可能性の直観的な概念と同一視するという提案は、本稿で初めて述べたものである（ただし、下記の§7の最初の脚注を参照のこと）。

「クリーネの方法（ American Journal of Mathematics 、1935年）を用いれば、本論文の考察は、再帰性の概念を用いることなく、比較的わずかな修正を加えるだけで、λ定義可能性の観点から完全に展開できる。一方、本論文の結果が得られた後には、クリーネ（近刊予定の論文「自然数の一般再帰関数」を参照）によって、λ定義可能性を用いることなく、再帰性の観点から同様の結果が得られることが示された。しかしながら、このように大きく異なり、（著者の見解では）同様に自然な有効計算可能性の定義が等価であることが判明したという事実は、これらが、この概念の通常の直観的理解と矛盾しない、この概念の一般的な特徴付けを構成すると信じるに足る、以下に述べる理由の強さを増すものである。」^{[ 29 ]}

脚注9は、セクション§4「再帰関数」にあります。

「⁹この[再帰的]の定義は、1934年にニュージャージー州プリンストンでの講義でクルト・ゲーデルが提案した再帰関数の定義と密接に関連しており、またその定義から着想を得たものである。ゲーデル自身も、この定義の一部はジャック・エルブランの未発表の提案によるものだと述べている。現在の再帰性の定義がゲーデルの定義と異なる主な特徴は、SC・クリーネによるものである。」

「クリーネによる近刊予定の論文『自然数の一般再帰関数』では、…現在の意味で再帰的な関数はすべてゲーデル（1934）の意味で再帰的であり、その逆もまた然りである。」^{[ 30 ]}

チャーチの論文「初等整数論の解決不可能な問題」（1936年）より少し前に、ゲーデルとチャーチの間で、λ定義可能性が「アルゴリズム」と「有効計算可能性」の概念を定義するのに十分かどうかについての議論が交わされた。

Church (1936) の「有効計算可能性の概念」という章の §7 には、次のような脚注 18 があります。

「¹⁸有効計算可能性と再帰性の関係（ここでは、この2つの概念を同一視することで答えようと提案されている）の問題は、著者との会話の中でゲーデルによって提起された。有効計算可能性とλ定義可能性の関係に関する対応する問題は、以前に著者によって独自に提案されていた。」^{[ 31 ]}

教会を「同一視する」とは、「同一性を確立する」ことではなく、「同一になるようにする」、「（精神、見解、原則において）一致していると考える」（他動詞形）、そして（自動詞形）「同じになる」ことを意味する。^{[ 32 ]}

ポストは、再帰が「実効計算可能性」の適切な定義であるかどうかについて疑問を抱いており、さらにチャーチの論文が発表されたことで、1936年の秋に「心理的忠実性」を備えた「定式化」を提案するに至った。作業者は「一連の空間またはボックス」^{[ 33 ]}を移動し、各ボックス内の紙に機械のような「原始的な行為」を実行する。作業者には「固定された変更不可能な指示のセット」が備わっている。^{[ 33 ]}各指示は、(1)識別ラベル/番号、(2)操作、(3)次の指示 j _iの3つまたは4つの記号で構成される。ただし、指示が​​タイプ(e)で、判定が「はい」の場合は指示 j _i '、そうでなければ「いいえ」の場合は指示 j _{i '}となる。 「原始的な行為」^{[ 33 ]}は、次の5つのタイプのうちの1つだけです。(a) 自分がいるボックス内の紙に印をつける（または既に印がついている紙に重ねて印をつける）、(b) 印を消す（または重ねて消す）、(c) 右に1部屋移動する、(d) 左に1部屋移動する、(e) 紙に印がついているか空白かを判定する。作業者は開始部屋のステップ1から始め、指示に従って行動します。（詳しくは「ポスト・チューリングマシン」を参照。）

序論で「直観的理論」について触れたこの問題は、ポストがチャーチを痛烈に批判するきっかけとなった。

「筆者は、この定式化がゲーデル＝チャーチの発展における意味での再帰性と論理的に等価であると見なしている。7^しかし、その目的は、ある種の論理的効力を持つ体系を提示することだけでなく、限定された領域において心理的忠実性も持つ体系を提示することにある。後者の意味では、より広範な定式化が想定されている。一方、我々の目的は、そのようなすべての定式化が論理的に定式化1に還元可能であることを示すことである。我々は現時点で、この結論を作業仮説として提示する。そして、我々の考えでは、チャーチが実効計算可能性を再帰性と同一視しているのはまさにこのことである。8 ^」（原文ではイタリック体）

⁷ [彼は証明へのアプローチを概説する]

⁸「チャーチ、ロック、前掲書、346、356-358頁参照。実際、チャーチらが既に行った研究は、この同一性を作業仮説の段階をはるかに超えて進めている。しかし、この同一性を定義の下に覆い隠すことは、ホモ・サピエンスの数学的能力の限界に関する根本的な発見がなされたという事実を隠蔽し、その継続的な検証の必要性を見えなくしてしまう。」^{[ 34 ]}

言い換えれば、ポストは「あなたがそう定義したからといって、それが本当にそうであるとは限らない。あなたの定義は単なる直観に基づいているにすぎない」と言っているのだ。ポストは定義以上のものを探していた。「上記のプログラムの成功は、我々にとって、この仮説を定義や公理というよりも、自然法則へと変えることになるだろう。そうして初めて、ゲーデルの定理とチャーチの結果は、すべての記号論理とすべての解法に関する結論へと変換されるのだ」^{[ 35 ]}

この論争的な姿勢は、1939年のアラン・チューリングの著作に不機嫌な形で表れており、ゲーデル、ガンディ、ジークの著作にも再び現れることになる。

A.M.チューリングの論文「計算可能な数について、決定問題への応用」は、 1936年11月にロンドン数学会で発表された。ここでも読者は注意すべき点がある。チューリングが用いた「コンピュータ」という言葉は人間を指し、「コンピュータ」の動作を「計算」と呼んでいる。例えば、彼は「計算は通常、紙に特定の記号を書くことによって行われる」（ 135ページ）と述べている。しかし、彼は機械の定義の文脈で「計算」という言葉^{[ 36 ]}を使用しており、「計算可能な」数の定義は次のとおりである。

「計算可能な数とは、小数で表した式が有限の手段で計算可能な実数と簡単に説明できる。私の定義によれば、小数を機械で書き表すことができる数であれば、その数は計算可能である。」^{[ 37 ]}

チューリングは「機械」をどのように定義したのでしょうか。チューリングは2つの定義を与えています。1つ目は§1「計算機」の要約で、もう1つは§9.Iで、人間の「コンピュータ」の動作をより詳細に分析した結果、非常によく似た定義となっています。定義§1に関して、彼は「正当化の根拠は、人間の記憶が必然的に制限されているという事実にある」^{[ 38 ]}と述べており、§1の最後に「すべて」という言葉を使って、彼が提案した機械を断言しています。

「これらの操作［テープスクエアにシンボルを書き込む、シンボルを消去する、1マス左にシフトする、1マス右にシフトする、シンボルをスキャンする、スキャンしたシンボルの結果としてマシン構成を変更する］には、数値の計算に使用されるすべての操作が含まれるというのが私の主張です。」^{[ 36 ]}

上記の括弧内の「1」という単語を強調しているのは意図的なものです。§9.Iに関して、彼は機械がより多くの正方形を調べることを許可しています。彼が主張するのは、この「より多くの正方形」を調べるという行動こそが、コンピュータ（人間）の行動を典型的に表しているということです。

「この機械は、コンピュータが観測した B 個のマスに対応する B 個のマスをスキャンします。どの操作においても、この機械はスキャンされたマスのシンボルを変更したり、スキャンされたマスのいずれかを、他のスキャンされたマスから L マス以内離れた別のマスに変更したりすることができます。… 上記の機械は、§2 [sic] で定義された計算機と本質的に大きな違いはなく、この種の機械に対応して、同じシーケンス、つまりコンピュータによって計算されたシーケンスを計算する計算機を構築することができます。」^{[ 39 ]}

チューリングは§2で「計算機」を次のように定義している。(i) §1で定義された「機械」（「自動機械」）に、次の制約(ii)を追加したもの: (ii) 2種類の記号（数字0と1）とその他の記号を出力する。数字0と1は「機械によって計算されたシーケンス」を表す。^{[ 36 ]}

さらに、数値が「計算可能」とみなされるためには、機械が無限個の0と1を出力する必要があります。そうでない場合は「循環的」とみなされ、そうでない場合は「循環的ではない」とみなされます。

「ある数が計算可能であるとは、円のない機械によって計算された数と整数だけ異なる場合をいう。」^{[ 40 ]}

チューリングはそれを「テーゼ」とは呼ばないものの、自身の「計算可能性」がチャーチの「有効計算可能性」と同等であることを証明しようとしている。

「最近の論文で、アロンゾ・チャーチは「有効計算可能性」という概念を導入したが、これは私の「計算可能性」と同等だが、定義は大きく異なっている。「計算可能性」と「有効計算可能性」の等価性の証明は、本論文の付録に概説されている。」^{[ 38 ]}

付録：計算可能性と実効計算可能性は次のように始まります。ここで彼が再帰について言及していないことに注目してください。実際、彼の証明の概略では、彼のマシンがλ計算で記号列を処理し、計算が彼のマシンの「完全な構成」を処理するのですが、どこにも再帰については言及されていません。マシン計算可能性と再帰の等価性の証明は、クリーネ（1943年と1952年）まで待たなければなりません。

「すべての実効的に計算可能な（λ定義可能な）数列は計算可能であるという定理とその逆は、以下に概略的に証明される。」^{[ 41 ]}

ガンディ（1960）はこの大胆な証明スケッチをチャーチのテーゼと混同しているようだ。1960年と1995年を参照のこと。さらに、チューリングの定義を注意深く読むと、チューリングは§1で提案した機械の「操作」が任意の計算可能な数を計算するのに十分であると主張しており、§9.Iで提示された人間の「コンピュータ」の動作を模倣する機械は、この提案された機械の一種であることがわかる。この点はチューリングによって1939年に改めて述べられる。

アラン・チューリングの膨大なプリンストン大学博士論文（指導教官：アロンゾ・チャーチ）は、『順序数に基づく論理体系』というタイトルで出版されている。その中で彼は、「実効的に計算可能」の定義を探求する過程を要約している。彼は太字で示されている定義を提案しており、これは「機械計算」と「実効的に計算可能」という概念を明確に区別（同一視）するものである。

「関数は、その値が何らかの純粋に機械的なプロセスによって求められる場合、『実効的に計算可能』であると言われます。この考え方を直感的に理解するのは比較的容易ですが、それでもなお、より明確で数学的に表現可能な定義を持つことが望ましいです。このような定義は、 1934年にプリンストン大学のゲーデルによって初めて与えられました…。これらの関数は、ゲーデルによって「一般再帰的」と表現されています…。実効的計算可能性の別の定義は、チャーチによって与えられており、彼はそれをλ定義可能性と同一視しています…。著者は最近、直感的な考え方により近い定義を提案しました（チューリング[1]、ポスト[1]も参照）。上記で述べたように、「関数は、その値が何らかの純粋に機械的なプロセスによって求められる場合、実効的に計算可能である」。この記述を文字通りに解釈し、純粋に機械的なプロセスとは、機械によって実行可能なプロセスであると理解することができます。これらの機械の構造を、ある標準形式で数学的に記述することが可能です。これらの考え方の展開は、著者の定義につながります。計算可能な関数、そして計算可能性†と実効計算可能性の同一視。これら３つの定義が等価であることを証明するのは、多少手間はかかるものの、難しくはない。^{[ 42 ]}

「† 我々は「計算可能な関数」という表現を、機械によって計算可能な関数を意味するものとし、「実質的に計算可能」とは、これらの定義のいずれかに特に限定されることなく、直感的な概念を指すものとする。我々は、計算可能な関数が取る値を自然数に限定しない。例えば、計算可能な命題関数も存在する可能性がある。」^{[ 43 ]}

これは力強い表現です。「同一性」とは、実際には必要かつ十分な条件を明確に述べたものであり、言い換えれば、「機能」「機械」「計算可能」「実効的に計算可能」という言葉にどのような解釈が与えられるか以外には、同一性には他の偶発的な要素は存在しないからです。

すべての関数について: 「この関数は機械で計算可能」ならば「この関数は実質的に計算可能」であり、「この関数は実質的に計算可能」ならば「この関数は機械で計算可能」である。

JB Rosserの論文「ゲーデルの定理とチャーチの定理の証明に関する非公式な解説」^{[ 44 ]}には、次のように述べられています。

「『効果的な方法』とは、各ステップが正確に予め定められており、有限ステップで必ず答えが得られる方法という、やや特殊な意味で用いられています。この特殊な意味において、これまでに3つの異なる厳密な定義が与えられています^{⁵。最も簡単に述べられる定義（} PostとTuringによるもの）は、ある一連の問題を解くための効果的な方法が存在するのは、質問を入力し、（後で）答えを読み取る以外に人間の介入なしに、その一連の問題のどれでも解ける機械を構築できる場合である、というものです。これら3つの定義はすべて同等であるため、どれを使用しても問題ありません。さらに、これら3つすべてが同等であるという事実は、いずれの定義も正しいという非常に強力な根拠となります。」

⁵ 1 つの定義は、チャーチがI [すなわち、チャーチ 1936初等整数論の解決不可能な問題] で与えている。もう 1 つの定義は、ジャック・エルブランとクルト・ゲーデルによるものである。それは I、脚注 3、p. 346 に記載されている。3 番目の定義は、E.L. ポストと A.M. チューリングによって、わずかに異なる 2 つの形式で独立して与えられた。最初の 2 つの定義は I で同等であることが証明されている。3 番目の定義は、A.M. チューリングのComputability and λ-definability [ Journal of Symbolic Logic、vol. 2 (1937)、pp. 153-163] で最初の 2 つの定義と同等であることが証明されている。^{[ 45 ]}

クリーネは論文「再帰述語と量化子」の中で「一般再帰関数」と「部分再帰関数」を定義している。表現関数、μ演算子などが登場する。彼は第12節「アルゴリズム理論」で、後に1952年にチャーチのテーゼと呼ばれることになる有名なテーゼIを述べている。

「この発見的事実と、記号的アルゴリズム処理の性質に関するいくつかの考察から、チャーチは次のテーゼを述べた^²²。同じテーゼはチューリングの計算機の説明にも暗黙のうちに含まれている^²³ 。

「テーゼI. 効果的に計算可能な関数（効果的に決定可能な述語）はすべて一般的に再帰的である。

「実質的に計算可能（実質的に決定可能）という用語の正確な数学的定義が欠けていたため、このテーゼを、既に受け入れられている、その逆の原理とともに、その定義として採用することができる。このテーゼは仮説の性格を持っている。この点はポストとチャーチ²⁴によって強調されている。

²²教会 [1] [初等整数論の解決不可能な問題] ^{[ 46 ]}

²³チューリング [1] [計算可能な数について、決定問題への応用(1936)] ^{[ 47 ]}

²⁴ポスト [1、p. 105]、^{[ 48 ]}およびチャーチ [2] ^{[ 49 ]}

クリーネは第60章で、「チャーチのテーゼ」を次のように定義している。

「…ヒューリスティックな証拠やその他の考察から、チャーチは1936年に以下のテーゼを提唱した。」

「テーゼI. 効果的に計算可能な関数（効果的に決定可能な述語）はすべて一般的に再帰的である。

「このテーゼは、チューリング（1936-7年）とポスト（1936年）によって定式化された計算機の概念にも暗黙のうちに含まれている。」 ^{[ 50 ]}

317ページで彼は上記の論文を「チャーチの論文」と明言している。

「§ 62. チャーチのテーゼ。この章と次の章の主な目的の1つは、チャーチのテーゼ（テーゼI §60）の証拠を提示することである。」^{[ 51 ]}

チューリングの「定式化」について、クリーネは次のように述べている。

「したがって、チューリングの定式化は、チャーチのテーゼ（同等の用語）の独立した記述を構成している。ポスト1936は同様の定式化を示した。」^{[ 52 ]}

クリーネは、チューリングが示したこととして、「チューリングの計算可能な関数（1936-1937）とは、彼の分析によれば、あらかじめ割り当てられた指示に従って動作する人間のコンピュータが実行できるあらゆる種類の操作を再現するように設計された種類の機械によって計算できる関数である」と提唱している。^{[ 53 ]}

クリーネはチューリングのテーゼを次のように定義している。

「§ 70. チューリングのテーゼ。チューリングの定義の下で、すなわち彼の機械のいずれかによって計算可能であると自然にみなされるすべての関数は、定理 XXX によりチャーチのテーゼと等価である。」

実際、この記述の直前に、クリーネは定理XXXを述べている。

「定理XXX（＝定理XXVIII＋XXIX）。以下の部分関数クラスは同程度である、すなわち同じ要素を持つ。（a）部分再帰関数、（b）計算可能関数、（c）1/1計算可能関数。同様に、l［小文字のL］は完全に定義された仮定関数Ψである。」

ゲーデルは、 1931年の論文「形式的に決定不可能な命題について」に、1963年8月28日付の注釈を追加し、「形式体系」の代替的な形式／表現に関する自身の見解を明確にした。彼は1964年に、その見解をさらに明確に繰り返している（下記参照）。

1963年8月28日追記。その後の進歩、特にAMチューリングの研究⁶⁹により形式体系の一般概念⁷⁰の正確かつ疑いなく適切な定義を与えることができるようになったことから、定理VIおよびXIの完全な一般版が可能になった。すなわち、一定量の有限数論を含むすべての無矛盾な形式体系には決定不能な算術命題が存在し、さらに、そのような体系の無矛盾性は体系内で証明できないことが厳密に証明できる。

「⁶⁹チューリング 1937、p. 249を参照。

「⁷⁰私の意見では、「形式体系」または「形式主義」という用語は、この概念以外には決して使用されるべきではない。プリンストンでの講演（プリンストン大学 1946、p. 11 に記載 [Davis 1965、pp. 84-88 [すなわち Davis p. 84-88] を参照]）で、私は形式主義の超限一般化をいくつか提案したが、これらは用語の適切な意味での形式体系とは根本的に異なるものであり、形式体系の特徴は、原理的には、それらにおける推論を機械装置で完全に置き換えることができることである。」^{[ 54 ]}

ゲーデル 1964 –プリンストン大学高等研究所での1934 年の講義ノートへのゲーデルの追記^{[ 55 ]}では、チャーチのλ 定義可能性と再帰によって定義される計算可能性の有効性についての彼のあまり好意的ではない意見が繰り返されているが、さらに大胆な言葉で繰り返している(以下で複数形の「定義」を使用していることから、両方とも軽視されていると推測せざるを得ない)。これはマーティン・デイビスへの手紙の中で (おそらく彼が『決定不能なもの』をまとめている最中) 書かれたものである。いくつかの表現の繰り返しは印象的である。

「その後の進歩、特にA.M.チューリングの研究により、形式体系の一般概念の正確かつ疑いなく適切な定義を与えることができるようになった結果、一定量の有限数論を含むすべての一貫性のある形式体系について、決定不能な算術命題の存在と、同一体系における体系の一貫性の証明不可能性を厳密に証明することができるようになった。」

「チューリングの研究は、「機械的手順」（別名「アルゴリズム」または「計算手順」または「有限組み合わせ手順」）の概念の分析を提供している。この概念は、「チューリングマシン」の概念と同等であることが示されている。* 形式システムは、証明可能な式と呼ばれる式を生成するための任意の機械的手順として単純に定義できる。形式システムの概念の本質は、推論が式に対する機械的操作によって完全に置き換えられることである。（アルゴリズムと同等ではない有限の非機械的手順が存在するかどうかという問題は、「形式システム」および「機械的手順」の定義の妥当性とは全く関係がないことに注意。）

「...もし「有限手順」が「機械的手順」を意味すると理解されるならば、脚注3で提起された質問は、§9で定義された再帰性については肯定的に答えることができ、これは今日定義されている一般的な再帰性と同等である（SC Kleene（1936）を参照...）」^{[ 56 ]}

「*チューリング1937 ...およびほぼ同時期のELポストの論文(1936)...を参照。計算可能性の以前の同等の定義については、ただし、それらは我々の目的にはあまり適していないので、A.チャーチ1936...を参照。」^{[ 57 ]}

脚注3は1934年の講義ノート本文中にあります。

「³スキーム（2）による再帰に加えて、他の形式（例えば、2つの変数に関して同時に）の再帰が許容される場合、その逆も真であるように思われる。有限計算の概念が定義されていないため、これは証明できないが、ヒューリスティックな原理として機能する。」^{[ 58 ]}

デイビスは、「実際、ゲーデルの定義（再帰の定義）とクリーネの定義（1936年）の等価性は、それほど自明ではない。したがって、一見そうは見えないかもしれないが、これらの講義の脚注3はチャーチのテーゼの記述ではない」と指摘している。^{[ 59 ]}

ロビン・ガンディの影響力のある論文「チャーチのテーゼとメカニズムの原理」は、バーワイズ他編の論文集に掲載されている。ガンディは、チャーチのテーゼを次のような意外な形で表現することから始めている。

1. はじめに

本稿では、「計算可能」とは直感的に与えられた概念を指し、「計算可能」とは「チューリングマシンで計算可能」を意味するものとします。もちろん、「計算可能」には他にも多くの同等の定義が存在します。

「チャーチのテーゼ。効果的に計算可能なものは、計算可能である。」

「…チャーチとチューリングはどちらも、抽象的な人間が何らかの機械的な補助具（紙と鉛筆など）を使用して計算することを念頭に置いていた」^{[ 60 ]}

ロバート・ソア（1995年、下記参照）はこの枠組みに疑問を呈し、チューリングの「付録証明」（1937年）よりも前に発表されたチャーチの論文（1936年）を問題視した。

ガンディは「機械的プロセスを分析し、以下のことを論証しようと試みている」。

「テーゼM. 機械で計算できるものは計算可能である。」^{[ 61 ]}

ガンディは「本質的にアナログ機械である装置を考慮から除外している。機械装置に関してなされる唯一の物理的前提（下記の原理IVを参照）は、装置のすべての原子部分の線形寸法に下限があり、変化の伝播速度に上限（光速）があるということである」^{[ 62 ]} 。しかし、彼はさらに機械を制限している。

（２）第二に、機械装置による計算の進行は離散的な用語で記述できると仮定し、したがって、検討対象の装置は、大まかに言えばデジタルコンピュータである。

「（３）最後に、デバイスは決定論的であると仮定します。つまり、デバイスの初期状態の完全な記述が与えられれば、その後のデバイスの挙動は一意に決定されます。」^{[ 62 ]}

彼は実際、この「テーゼM」を擁護する議論を展開しており、それを「定理」と呼んでいる。その中で最も重要な「原理」は「原理IV：局所的因果関係の原理」である。

「さて、ここで我々の最も重要な原則について述べよう。チューリングの分析では、動作が記録の限られた部分のみに依存するという要件は、人間の限界に基づいていた。我々はこれを、局所的因果律の原理と呼ぶ物理的な限界に置き換える。その正当性は、効果と信号の伝播速度が有限であることにある。現代物理学は、遠隔での瞬間的な動作の可能性を否定している。」^{[ 63 ]}

1985年に「テーゼM」が量子チューリングマシンに適用され、チャーチ・チューリング・ドイチュ原理が導き出された。^{[ 64 ]}

ソアレによる計算可能性と再帰に関する徹底的な考察^{[ 65 ]}が掲載されている。彼は、計算可能性の「はるかに不適切な」定義に関して、ゲーデルの1964年の意見（上記）を引用し、さらに次のように述べている。

クリーネは[1981b、p.49]、「チューリングの計算可能性は本質的に説得力がある」が、「λ定義可能性は本質的に説得力があるわけではなく」、「一般的な再帰性はほとんど説得力がない（その著者であるゲーデルは当時全く納得していなかった）...。今日ではほとんどの人がチューリングのテーゼを受け入れている」^{[ 66 ]と書いている。}

ソアレの脚注7（1995年）もガンディの「混乱」を指摘しているが、どうやらそれはガンディ（1988年）にも続いているようだ。この混乱は研究や思考における重大な誤りであり、彼のプログラム全体に暗い影を落としている。

「⁷ガンディは実際にはここで書かれている「チューリングのテーゼ」ではなく「チャーチのテーゼ」と書いたが、チューリングは1936年にも他のどこにも一般的な再帰関数について何も証明していないので、ガンディは少なくとも意図的には後者を意味していたに違いない。」^{[ 67 ]}

ブレガーは、ある概念に「公理的に」アプローチする場合に問題が生じることを指摘している。つまり、「公理系」には、公理セットが提示されたときに明示されない、一つまたは複数の暗黙の公理が埋め込まれている可能性があるということである。

例えば、知識（および能力）を持つ能動的な主体は、あらゆる公理系における（潜在的な）基本公理となり得る。「人間のノウハウが必要である。それは公理では形式化されていないノウハウである。¶ ... 記号に関するノウハウを持つ人間なしに、純粋に形式的な記号体系としての数学は不可能である...」^{[ 68 ]}

彼はヒルベルトの言葉を引用している。

「1905年に行われた大学講義で、ヒルベルトは論理学の公理を述べる前に「思考の公理」または「知性の存在の公理」を持つことが「絶対に必要」だと考えた。原稿の余白に、ヒルベルトは後に「哲学者のアプリオリ」と書き加えた。彼はこの公理を次のように定式化した。「私は対象について考え、a、b、…、x、y、…のような単純な記号を用いてそれらを表現することで、曖昧さなく認識できるようにする能力を持っている。私の思考は、ある一定の規則に従ってこれらの対象とある一定の方法で作用し、私の思考は自己観察によってこれらの規則を検出し、これらの規則を完全に記述することができる」[(ヒルベルト 1905、219)；(ペックハウス 1990、62fおよび227も参照)]」^{[ 69 ]}

ブレガーは、ジュゼッペ・ヴェロネーゼ（1891）とヘルマン・ワイル（1930-1）の例を挙げて、さらに自身の主張を裏付けている。彼は、公理集合を特定の言語、つまり行為者が知っている言語（例えばドイツ語）で表現するという問題について議論を続けている。^{[ 70 ] [ 71 ]}

これについては、「アルゴリズムの特性」の項、特に、いかなる計算においても、使用される記号に意味を与える観察者が存在しなければならないというサールの見解を参照してください。

「フェファーフェスト」（ソロモン・フェファーマンの70歳の誕生日）で、ウィルフリード・ジークは、 2年前に書かれた「人間と機械による計算：概念分析」というタイトルの論文を初めて発表した。この論文は（Sieg et al. 2002:390–409）に再録されている。ジークは以前、「機械的手順と数学的経験」（George 1994、p. 71ff）を発表しており、リチャード・デデキントから始まり、1950年代のアラン・チューリングとスティーブン・コール・クリーネの後期の論文で終わる 「計算可能性」の歴史を紹介している。フェファーフェストの論文は、以前の論文の主要なポイントを要約し、主にロビン・ガンディの1980年の論文に焦点を当てている。ジークは、チューリングの「ストリングマシンによる計算可能性」（人間の「コンピュータ」）をメカニズム「文字マシンによる計算可能性」 ^{[ 72 ]}に還元し、ガンディの並列マシンに拡張している。

ジークは、「コルモゴロフとウスペンスキーのアルゴリズムに関する研究」や（デ・ピサピア 2000）、特にKUポインターマシンモデル、人工ニューラルネットワーク^{[ 73 ]}など、より最近の研究を引用し、次のように主張している。

「非形式的な概念分析と数学的等価証明を分離することは、チューリングのテーゼ（一般的に解釈した場合）の正しさが2つの柱、すなわちコンピュータの有界性と局所性の条件の正しさと、関連する中心テーゼの正しさに基づいていることを認識するために不可欠である。後者は、コンピュータの計算が特定の種類の機械によって直接模倣できることを明示的に主張している。この分析的議論の筋道がどれほど満足のいくものであっても、2つの弱点がある。それは、制約条件の緩さ（記号構成とは何か？機械的操作によってどのような変化が生じるのか？）と、それに伴う中心テーゼの曖昧さである。我々は、どのような姿勢をとっても、方法論的にまだ不十分な立場にある…」^{[ 73 ]}

彼は「特定のタイプの構成や操作からさらに抽象化することによって、より満足のいく立場へと一歩踏み出す」と主張している^{[ 73 ]。}

「チューリングが機械の計算を分析したとよく言われるが、それは歴史的にも体系的にも不正確である。私の説明で明らかになったはずだ。機械の計算を特徴づけたのは、1980年にチューリングの弟子であるロビン・ガンディだけである。」^{[ 73 ]}

上記の記述が真実かどうかは読者の判断に委ねられる。ジークは続けてガンディの分析について述べている（上記1980年を参照）。その際、彼は「ガンディ・マシン」と呼ぶものを形式化しようと試みている（付録に詳細な分析がある）。ガンディ・マシンについて：

「…ガンディマシンの定義は、並列計算の特性を具現化した「抽象的な」数学的定義である。…第二に、ガンディマシンは群や位相空間と同様に、抽象的な公理的定義の一般的な特徴、すなわち、多様な解釈が可能であるという特徴を共有している。第三に、…任意のガンディマシンの計算は文字マシンでシミュレートすることができ、公理的概念の表現定理として理解するのが最適である。」[太字追加]

「公理的アプローチは、計算プロセスの本質を抽象的な方法で捉えています。私が説明してきた2種類の計算機の違いは、チューリング計算機は状態の限られた部分を変更するのに対し、ガンディマシンは任意の数の限られた部分に対して並列に動作するという事実に集約されます。表現定理は、公理のモデルが文字多様体におけるチューリングマシンと計算的に等価であることを保証します。」^{[ 74 ]}

• Barwise, Jon、HJ Keisler、K. Kunen編、1980 年、『クリーネ・シンポジウム』、426 ページ、North-Holland Publishing Company、アムステルダム、ISBN 0-444-85345-6
• Church, A. , 1936a、（Davis 1965:88ff）、「初等整数論の解決不可能な問題」
• Church, A., 1936b, in (Davis 1965:108ff), "Entscheidungsproblemに関する注記"
• Church, A., 1938, 「構成的第二数クラス」、Bull. Amer. Math. Soc. vol. 44, Number 4, 1938, pp.  224–232]
• Davis, Martin編、1965 年、『決定不能なもの：決定不能な命題、解決不能な問題、計算可能な関数に関する基本論文』、Raven Press、ニューヨーク、 ISBN 0-911216-01-4この記事で言及されているゲーデル、チャーチ、チューリング、ロッサー、クリーネ、ポストらの論文を含む、すべての原著論文がここに収録されている。ほとんどの論文には、デイビスによる貴重な解説が付されている。
• デイビス、マーティン、2001年、『論理のエンジン：数学者とコンピュータの起源』、WWノートン＆カンパニー、ニューヨーク、ISBN 0-393-04785-7pbk。
• ジョン・ウィリアム・ドーソン・ジュニア、1997年、『論理的ジレンマ：クルト・ゲーデルの生涯と業績』、361ページ、AKピーターズ、マサチューセッツ州ウェルズリー、ISBN 1-56881-025-3、QA29.058D39。
• ジョン・ウィリアム・ドーソンおよびジョン・ウィリアム・ドーソン・ジュニア、2005年、『論理的ジレンマ：クルト・ゲーデルの生涯と業績』、362ページ、AKピーターズ、マサチューセッツ州ウェルズリー、ISBN 978-1-56881-025-6
• De Pisapia, N., 2000, Gandy Machines: チューリングマシン、ライフゲーム、人工ニューラルネットワークのための並列計算の抽象モデル、修士論文、カーネギーメロン大学、ピッツバーグ。
• ダーショウィッツ、ナフム、グレヴィッチ、ユーリ、2007年、「チャーチのテーゼの自然な公理化」、https://research.microsoft.com/~gurevich/Opera/188.pdf
• Deutsch, D. (1985), "Quantum theory, the Church–Turing principle and the universal quantum computer"(PDF), Proceedings of the Royal Society, 400 (1818): 97–117, Bibcode:1985RSPSA.400...97D, CiteSeerX 10.1.1.41.2382, doi:10.1098/rspa.1985.0070, S2CID 1438116, archived from the original(PDF) on 9 March 2016, retrieved 17 August 2011
• Gandy, Robin, 1978, Church's Thesis and the Principles for Mechanisms, in (Barwise et al. 1980:123-148)
• George, Alexander (+ed.), 1994, Mathematics and Mind, 216 pages, New York, Oxford University Press, ISBN 0-19-507929-9
• Gödel, K., 1930, in (van Heijenoort 1967:592ff), Some metamathematical results on completeness and consistency
• Gödel, K., 1931a, in (Davis 1965:4-38), On Formally Undecidable Propositions of the Principia Mathematica and Related Systems. I.
• Gödel, K., 1931b, in (van Heijenoort 1976:616ff) On completeness and consistency
• Gödel, K., 1934, in (Davis 1965:39-74), On Undecidable Propositions of Formal Mathematical Systems
• Gödel, K., 1936, in (Davis 1965:82ff), On The Length of Proofs, "Translated by the editor from the original article in Ergenbnisse eines mathematishen Kolloquiums, Heft 7 (1936) pp. 23-24." Cited by Kleene (1952) as "Über die Lāange von Beweisen", in Ergebnisse eines math. Koll, etc.
• Gödel, K., 1964, in (Davis 1965:71ff), Postscriptum
• Groshoz, Emily and Breger, Herbert, 2000, The Growth of Mathematical Knowledge, 416 pages, Kluwer Academic Publishers, Dordrect, The Netherlands, ISBN 0-7923-6151-2.
• Hawking, Stephen, 2005, God Created the Integers: The Mathematical Breakthroughs that Changed History, Edited, with Commentary by Stephen Hawking, Running Press, Philadelphia, ISBN 0-7624-1922-9
• Hodges, Andrew, 1983, Alan Turing:The Enigma, 1st edition, Simon and Schuster, New York, ISBN 0-671-52809-2
• Kleene, S. C., 1935, in (Davis 1965:236ff) General Recursive Functions of Natural Numbers
• Kleene, S. C., 1971, 1952 (10th impression 1991) Introduction to Metamathematics, 550 pages, North-Holland Publishing Company (Wolters-Noordhoff Publishing) ISBN 0-7204-2103-9
• Merriam-Webster Inc.、1983年、『Webster's Ninth New Collegiate Dictionary』、1563ページ、Merriam-Webster Inc.、マサチューセッツ州スプリングフィールド、ISBN 0-87779-509-6
• Post, EL、1936年、（Davis 1965:288ff）「有限組み合わせプロセス - 定式化1」または「記号論理学ジャーナル」、第1巻、第3号（1936年9月）、 103～105ページ。
• Rosser. JB、1939年、「ゲーデルの定理とチャーチの定理の証明に関する非公式な解説」、The Journal of Symbolic Logic、第4巻（1939年）、53-60頁、 および（Davis 1967:223-230）に再録。
• ジーク、ウィルフリード、リチャード・ゾンマー、キャロリン・タルコット（編）、2002年、『数学の基礎に関する考察：ソロモン・フェファーマンを記念する論文集』、Lecture Notes in Logic 15、444ページ、AK Peters, Ltd.、ISBN 1-56881-169-1
• Soare, Robert , 1996, Computability and Recursion , "Bulletin of Symbolic Logic 2", Volume 2, Number 3, September 1996, pp.  284–321. doi:10.2307/420992
• チューリング、AM（1937）[学会発表 1936年]、「計算可能な数について、決定問題への応用」（PDF）、ロンドン数学会紀要、第2巻、第42巻、 230～ 265 ページ、 doi：10.1112/plms/s2-42.1.230、S2CID 73712  およびチューリング、AM（1938）。「計算可能な数について、決定問題への応用：訂正」。ロンドン数学会紀要。2. 第43巻（1937年発行）。pp. 544–6。doi ： 10.1112 /plms / s2-43.6.544。  （参照：デイビス 1965:115ff）
• チューリング、A.、1939年、（デイビス 1965:154ff）『順序数に基づく論理体系』
• ファン・ヘイエノールト、ジャン、1976年、『フレーゲからゲーデルへ：数理論理学の資料集』、116ページ、1879～1931年、第3刷、初版1967年、ハーバード大学出版局、マサチューセッツ州ケンブリッジ、ISBN 0-674-31844-7（ペーパーバック）

• 『記号論理学紀要』には、論文が掲載されているすべての巻へのリンクがオンラインで提供されています。
• アロンゾ・チャーチ、1938年、「建設的な第二数クラス」 「1937年12月29日にインディアナポリスで開催された学会の会合において、プログラム委員会の招待により行われた講演。」
• クルト・ゲーデル、1931年、『プリンキピア・マテマティカの形式的に決定不可能な命題および関連体系について I』。マルティン・ヒルツェル訳、2000年11月27日。
• エミール・L・ポスト、1946年、「再帰的に解けない問題の変種」
• ウィルフリード・ジーク、2005年、『教義なき教会：計算可能性のための公理』、 カーネギーメロン大学、 2006年8月21日にウェイバックマシンにアーカイブ済み
• ウィルフリード・ジーク、2000年、『人間と機械による計算：概念分析』、カーネギーメロン大学、 2011年6月10日にウェイバックマシンにアーカイブ済み
• ロバート・I・ソアレ、1995年、『計算可能性と再帰』
• Robert I. Soare、1996年、「計算可能性と再帰」、『記号論理学速報』第2巻、第3号、1996年9月に掲載。
• 高橋雅子、2004年、「一般再帰関数について」、国際キリスト教大学、特に参考文献を参照。
• A.M.チューリング、1936年、『計算可能な数について、決定問題への応用』