私の好きな著者（David Deutsch、Roger Penrose、Douglas Hofstadter）はすべて、計算理論の教会-チューリング論文、そしてもっと重要なことに、その最強の解釈：チューリング原理を掘り下げています。 この記事では、私は最初に素人の言葉で教会-チューリングの論文を説明します。
私がコンピュータサイエンスの学位を取得していたとき、私は計算理論のクラスのイントロでチューリングマシンと教会-チューリング論文を勉強しました。 当時、私はそれが時間の大きな無駄だと思っていました。 私はちょうどコンピュータをプログラムしたかったし、私はこの長い死んだチューリング男（もこの教会の男）も彼の愚かな理論的なマシンについて
今、私は教会-チューリング論文の哲学的な影響を理解しているので、私はクラスで注意を払っていたことを願っています！ 教会-チューリングの論文は、真実であれば、いくつかの深遠な哲学的影響を持っており、それはまた、現実の深く特別な性質について何かを教えてくれるか
有限オートマトン
計算理論に関するすべてのテキストとクラスは、”有限オートマトン”と呼ばれるものから始まります。”それらの背後にある基本的な考え方は非常に簡単です。 選択をして状態間を移動できる単純な「機械」を想像してみてください。 硬貨作動させた回転木戸の「論理」を表す非常に簡単な1つの例はここにあります。
平易な英語では、これはロックされている回転木戸を押し抜こうとすると、最初にコインを入れていないと あなたがコインを入れているが、まだ押していない場合は、追加のコインはちょうどロック解除された状態でそれを残します。 あなたがコインを入れている場合は、押し通すことができます。 その後、次の人のために再びロックされます。
おそらく説明よりも図から理解しやすかったでしょう。
有限オートマトンは、これよりもはるかに複雑な論理を実行することができます。 しかし、これはあなたに有限オートマトンがどのように機能するかの基本的な感触を与えるはずです。
注意すべきことの一つは、上記のような有限オートマトンは、紙の上に泡と線の束としてのみ存在するため、純粋に理論的であるということです。 それはこれらの決定をする回転木戸の中の小さい”有限なオートマトン機械”があるようではない。 または多分私は回転木戸自体が有限なオートマトン機械であることを代りに言うべきである。
私たちが本当に望んでいたなら、おそらく有限オートマトンになる実生活で機械を構築することができます。実際の生活の中で実際のマシンとしてそれを構築し、回転木戸にそれをインストールするから誰かを停止するものは何もありません。 それはちょうどそれを行うための最も安い方法ではありません。
だから、あなたが有限オートマトンの図面として作る”プログラム”は、実際に働く実際の”計算”に変えることができます。 実際に存在することができる計算機（有限オートマトンのような）と、仮説的で物理学の法則に違反する計算機の違いの重要性は、一瞬で重要になります。
より強力なマシン
計算理論のクラスが進むにつれて、学生は有限オートマトンよりも強力なますます複雑な”機械”に導入されます。 右の図が示すように、次の最も強力なのはプッシュダウンオートマトン（PDA）です。 PDAは実際には単なるDFAであり、一種の「メモリ」が追加されています。 このメモリにより、PDAはdfaができない計算（またはプログラム）を作成して実行することができます。
重要な点は、決定論的有限オートマトン（DFA）に書 言い換えれば、PdaはDfaができない「プログラム」のクラスを表現できるため、Dfaよりも「強力」です。
だから、DfaとPdaの間には「計算能力」という関係があります。「つまり、DFAに書かれたプログラムはPDAにも書くことができることを証明することは可能ですが、その逆は真実ではありません。
証明は証明にあります
PDAがDFAができることを何でも実行できるという証明は、DFAのロジックをPDAにマップできるスキームを考え出すことによっ PDAは単なるメモリを備えたDFAなので、これは難しいことではありません-「メモリ機能」を使用しないでください。
しかし、その逆はどうですか？ PDA用に書かれた特定の種類の「プログラム」をDFAに変換することは不可能であることを証明できますか？ つまり、プッシュダウンオートマトンを有限オートマトンにマッピングできないという証拠はありますか？ または、PDAをFDAにマップする方法を現在知らないため、有限オートマトンがプッシュダウンオートマトンよりも強力ではないと仮定していますか？ PdaをFDAsにマップする方法があり、誰もそれを行う方法をまだ発見していないかもしれませんか？ それは少なくとも可能性ではないですか？
結局のところ、PDAがDFAでは実行できない特定の種類のプログラムをPDAが実行できることを証明することは可能です。 あなたがそれをする方法は、あなたが計算を見つけることです（すなわち DFAが計算できないことを証明し、PDAがそれを計算できることを実証することができます。
マシンの計算能力
この事実—より強力な（PDA）論理マシンとより強力でない（DFA）論理マシンがあるということ—それ自体興味深いことです。
しかし、それは哲学的な質問につながります：”最も強力な計算機”のようなものはありますか？”
そのような”最も強力なマシン”があった場合、どのようにして特定の提案されたマシンが”最も強力なマシン”であることを知ることができますか？”または、利用可能なコンピューティングマシンのちょうど異なるタイプがあり、あなたは仕事のために右のものを選択する必要がありますか？
チューリングマシン
では、PDAよりも強力なマシンは何ですか？
歴史が持つように、ほぼ同時に、Pdaよりも確かに強力な2つの非常に異なるタイプの「マシン」が提案されました。
1つはアラン-チューリングのチューリング-マシンだった。 もう一つは、マシンを開発するのと同じ目的を果たしたAlonzo Churchによって開発された巧妙な表記法のセットほどのマシンではありませんでした。 これらの2つの「機械」のうち、チューリングマシンは概念的に教える方が簡単なので、通常は計算理論コースで教えられる機械です。
チューリングマシンは、読み取り/書き込みヘッドと（仮想的な）紙テープを持ち、読み取りまたは書き込みが可能な面白い小さな理論的なマシンです。 チューリング-マシンが読み取る内容に基づいて、チューリング-マシンは、読み取り/書き込みヘッドを前方または後方に移動するか、テープ上の新しい位置から読み取るか、またはテープ上の新しい位置に書き込むかのいずれかのタスクの組み合わせを実行するアクション状態になります。 チューリングマシンは次のようになります:
チューリングマシンと現代のコンピュータ
興味深いのは、チューリングマシンは、表面的な外観にもかかわらず、実際には現代のコンピ 現代のコンピュータでは、中央処理装置（CPU）はチューリングマシンの読み取り/書き込みヘッドに相当します。 メモリチップ（RAMまたはROM）は、回転機械が読み書きできる長い紙テープのセルと非常によく似ています。 だから、現代のコンピュータはチューリングマシンとほぼ同等であるように見えます。
現代のコンピュータはチューリングマシンよりも一つの利点を持っています。 現代のコンピュータは、チューリングマシンのように、その「メモリ」の1つのセルから順番に移動する必要はありません。
チューリングマシンが一度に一つのセルしか移動できないという事実は、大きな制限のようですね。 私たちは、いくつかのマシンが他のマシンよりも論理的に”より強力”であることを見ました。 おそらく、チューリングマシンができないタスクを実行できるチューリングマシンよりも強力なマシンがありますか？ そして、現代のコンピュータは、セルからセルに順番に移動するのではなく、メモリを飛び回る能力のために、チューリングマシンができないいくつかのプ
実際、現代のコンピュータは、チューリングマシンが無限に長い紙テープ（すなわち無限のメモリ）を持っていると考えられていたという事実のために、チューリングマシンよりも表現力が低い。 しかし、人間は一般的に無限に長い結果を出す無限に長い計算に関心があるわけではないので、これはどのような種類の計算を実行できるかにほと 私は現代のコンピュータとチューリングマシンは”ほぼ”同等であると言う理由です。 実際、任意ではあるが有限のサイズのメモリを想定している限り、それらは実行できるプログラムの種類に関して正確に同等です。
教会チューリング論文：チューリングマシン=最大論理力
しかし、貧しいアロンゾ教会はどうですか？ チューリングマシンが教えることが容易であるため、彼のかわいそうな”マシン”は忘れ。 彼のマシンは、チューリングマシンができないいくつかの計算/プログラムを表現することができますか、またはその逆ですか？
Alan TuringとAlonzo Churchが2つの全く異なるタイプの理論計算機を作成し、どのタイプの計算を実行できるかという点でまったく同じことが起こったのであれば、星の偶然の一致ではないでしょうか？
だから、アラン-チューリングがチューリング-マシンのために書かれたプログラムは教会のマシンのために書かれることができるという証明と、教会のマシンのために書かれたプログラムはチューリング-マシンのために書かれることができるという証明を生成することができたとき、みんなの驚きを想像してみてください。
実際には、理論計算機にはいくつかのタイプが提案されています。 たとえば、理論家はチューリングマシンに複数のテープを読み書きできるようにしようとしました。 彼らはチューリングマシンに2次元の”シート”を読み書きできるようにしようとしました。 理論家はチューリングマシン（および教会のマシン）のあらゆる種類の改善を試みました。
そして、これまでのところ、それらが単純なチューリングマシンと同等であることを証明することが可能でした。
それは野生の偶然のように見えますよね？ そして、どのタイプの計算を実行できるかに制限された上限がない限り、それは野生の偶然でしょう。
このような上限がある場合、チューリングマシンとチャーチマシンと他のすべての計算機が提案したすべてが同じ計算能力を持っていることは全く偶然ではないでしょう。
しかし、チューリングマシンができない計算を実行する能力を持つ、まだ発見していない計算マシンがないことを証明することはできますか？
どのように、正確に、私たちはそのような証拠を生成しますか？ 事実は、チューリングマシンよりも強力なものは何もないことを証明することはできないということです。 だから、誰が知っている、多分あります。
しかし、実際には、そのような機械を見つける（または発明する）ことはできません。
だから、チューリングマシンの力を向上させる方法を見つけるために、かなりの努力を試み、失敗した後、最終的に教会-チューリングの論文は、それが真実であることが証明されていなかったにもかかわらず受け入れられました。 教会-チューリングの論文は本質的にこのようなことを言います:
普通の古いチューリングマシンができない論理プログラムを実行できる計算機を考え出すことはできません.
または他の言葉で:
チューリングマシンとその同等のものは、計算機の最も強力な可能なタイプであり、私たちがまだ知らないほど強力なものはありません。
この論文に関する何年もの研究の後、この論文はまだ基本的に保持しています。 私たちは、理論的な量子コンピュータの導入と論文への変更のややがあったことを後で表示されます。 しかし、基本的には、論文はまだ今日も当てはまります。 論理的な表現力に関しては、チューリングマシンよりも優れた方法を誰も考え出したことはありません。 チューリングマシンはまだ君臨チャンピオンです。
だから今、あなたは教会-チューリングの論文を理解しています。 しかし、教会-チューリングの論文は、チューリングの原則と実際には全く同等ではありません。 だから、将来の記事では、違いが何であるか、それが哲学的な影響であるかを開発します。
注
チューリング原理。 だから、それを信じていないRoger Penroseによって命名されました（少なくとも現在の形ではありません）。 それは、少なくとも彼の形でそれを信じているDavid DeutschによってTuring-Deutschの原則に発展しました。）（詳細はWikipediaの記事を参照）