チャーチ・チューリングのテーゼ
チャーチ＝チューリングのテーゼとは、直感的な計算可能性（Informal / Intuitive Notion of Computability）と数学的に厳密定義された計算可能性（Formal / Mathematical Notion of Computability）が等価であるという主張（定立・仮説）です。
- 直感的概念（直感的な計算）：
有限のステップで、曖昧さのない明確な規則（アルゴリズム）に従って機械的に答えを導出できること。 - 数学的概念（厳密な計算）：
チューリングマシンによって計算可能であること、あるいは、$\lambda$ 定義可能、$\mu$ 帰納的であること。
本テーゼは、人間が論理的・機械的な手順で実行可能な計算処理（アルゴリズム）は、すべてチューリングマシンで実現（シミュレート）可能である言うことができます。
「テーゼ」としての位置付け
本主張は数学的な定理（Theorem）ではなく、論理学的な仮説（Thesis）として扱われます。理由は、直感概念と厳密概念を結び付けたものであるためです。
チューリングマシンは、数学的に厳密に定義され、証明された概念です。一方で、人間が使うアルゴリズム（有限の機械的手順）という言葉は、日常言語・メタ数学における直感的な概念です。
定義されていない直感的な概念と厳密な数学的定義が等しいことは、原理的に数学の枠内では証明不可能です。そのため、証明された定理ではなく、計算可能性という概念の定義に関する合理的妥当性を提示した定立（テーゼ）として位置付けられます。
テーゼを支持する根拠
テーゼ自体は証明不能ですが、計算理論の分野において、事実上の標準（事実上の公理）として受け入れられているのには以下の根拠があります。
- 各計算モデルの完全同値性：
レジスタマシン、セル・オートマトン、現代のプログラミング言語など、考案されたあらゆる実用的・理論的計算モデルは、すべてチューリングマシンと高々等価（チューリング完全）に留まります。 - チューリングの分析の妥当性：
チューリングは1936年の論文で、人間が紙とペンを使って計算する際の心理的・物理的動作（状態の遷移、記号の視認・書込み）を最小単位に分解・抽象化し、チューリングマシンを導き出しました。 - 反例の不存（非計算可能問題の普遍性）：
直感的には解けるがチューリングマシンでは解けないという問題（反例）は、1930年代以降１度も発見されていません。
注意点
- 計算速度や計算効率について
チャーチ・チューリングのテーゼは、原理的に答えを算出可能（Computabilit）かという決定可能性の問題です。計算に必要な時間やメモリ空間量を扱う計算複雑性理論（Complexity Theory）とは区別されます。 - ハイパーコンピューティングとの関係
相対論的効果や無限精度実数を用いた理論上のハイパーコンピュテーションは、現実的に構成可能かという点で直感的なアルゴリズムの範囲を超えており、テーゼを否定するものではありません。 - 量子コンピュータとの関係
量子コンピュータは、一部の問題の計算スピード（複雑性）を高速化するもので、チューリングマシンで計算不可能な問題を計算できるわけではありません。量子計算も、チャーチ＝チューリングのテーゼの枠組み内に収まります。
計算可能性
数学的な計算可能性（Computability）とは、ある問題や関数が、明確に定められた手順（アルゴリズム）によって原理的に解けるか、あるいは、その手順によって解にたどり着く限界線を決定する学問です。
現実のコンピュータの処理速度やメモリ容量といった物理的制限を取り払い、時間と紙が無限にあれば理論上計算できるのかという可能性の根本的限界を扱います。
数学において関数 $f$ が計算可能であるとみなされるには、以下の条件を満たすアルゴリズム（計算手順）が存在する必要があります。
- 有限性: 手順（命令のリスト）が有限の長さで書かれていること。
- 明確性: 各ステップに一切の曖昧さがなく、機械的に実行できること。
- 停止性: 適切な入力に対して、有限回のステップで必ず計算が終了し、正しい出力を出すこと。
計算モデル
1930年代にいくつかのが提示され、これらが同値であることが証明されたことで、これらのモデルで実行できることが数学における計算可能性の厳密な定義となりました。
- チューリングマシン（Turing Machine）による計算可能性
アラン･チューリングが考案した抽象計算モデル。 - $\lambda$ 計算（Lambda Calculus）による $\lambda$ 定義可能性
アロンゾ・チャーチが提唱した $\lambda$ 計算（ラムダ計算）で、特定の関数が $\lambda$ 項（ラムダ項）を用いて評価・表現できる。 - $\mu$ 帰納的関数（$\mu$-Recursive Functions）
クルト・ゲーデルやスティーヴン・クリーネらが定式化した、数学の最小限のルールから組み立てられる計算可能な関数のクラス。
これらの計算モデルは、計算できる関数の集合が完全に同一（同値）であることが数学的に証明されました。これにより、これらと同値な計算モデルによりたどり着ける範囲が「計算可能」であると考えることができます。
決定可能性と計算可能性
計算可能性理論では、対象によって呼び方が区別されることがあります。対象が関数の場合、計算可能（Computable）とは、入力 $x$ を与えたとき、出力 $f(x)$ を返すアルゴリズムが存在することです。
一方、対象が問題（集合）の場合、決定可能（Decidable）とは、条件 $P$ を満たすかという Yes/No を求める問いに対し、常に正しい答えを出して停止するアルゴリズムが存在することです。
非計算可能問題
非計算可能問題とは、どれほど人類の技術や理論が進歩しても、アルゴリズムでは絶対に解けない問題（不可定問題）のことで、数学的に証明されました。代表的な例が停止性問題（Halting Problem）です。
停止性問題とは、任意のプログラム $P$ とその入力 $I$ を受け取り、$P(I)$ が有限時間で処理を終えて停止するか、それとも無限ループに陥るかを判定するプログラムを作れるかという問題です。
このような判定プログラム $H$ を作成することは論理的に不可能であることは、アラン・チューリングにより証明しました。
