計算可能な解析

タイプ2チューリングマシンは、3つのテープを備えたチューリングマシンです。入力テープは読み取り専用、作業テープは書き込みと読み取りが可能、そして特に重要なのは、追記専用の出力テープです。

この文脈では、実数は任意の無限の記号列として表現されます。これらの列は、例えば実数の桁を表すことができます。このような列は計算可能である必要はありません。この自由度は重要であり、哲学的にも問題ありません。^{[ 2 ]}ただし、これらの列に対して動作するプログラムは、合理的な意味で計算可能である必要があります。

実数の場合、通常の十進数表現や二進数表現は適切ではありません。代わりに、ブロウワーが最初に提案した符号付き数字表現がよく使用されます。数体系は基数2ですが、数字は${\displaystyle {\overline {1}}}$（${\displaystyle -1}$)、0と1。特に、これは${\displaystyle 1/2}$両方で表現できます${\displaystyle 0.1}$そして${\displaystyle 1.{\overline {1}}}$。

十進表記が不適切な理由を理解するために、計算の問題を考えてみましょう。${\displaystyle z=x+y}$どこ${\displaystyle x=0.(3)}$そして${\displaystyle y=0.(6)}$結果を表示${\displaystyle z}$小数表記で。${\displaystyle z}$どちらか${\displaystyle 0.(9)}$または${\displaystyle 1.(0)}$例えば後者の結果が与えられた場合、有限の数${\displaystyle n}$桁の${\displaystyle x}$数字を選択する前に読み取られます${\displaystyle 1}$小数点より前の${\displaystyle z}$— しかし、もし${\displaystyle n+1}$の 番目の桁${\displaystyle x}$2に減少すると、結果は${\displaystyle z}$間違いだろう。同様に、前者の選択肢も${\displaystyle 0.(9)}$のために${\displaystyle z}$時には間違っていることもあるだろう。これはまさにテーブルメーカーのジレンマだ。

符号付き数字の他に、原理的にはコーシー数列やデデキント切断の類似物を用いることもできる。

計算可能な関数は、タイプ2チューリングマシン上のプログラムとして表現されます。プログラムは、入力に関係なく、出力テープに任意の数の記号を書き込むのに有限時間しかかからない場合、完全プログラム（部分関数ではなく完全関数という意味で）とみなされます。完全プログラムは永久に実行され、出力の桁数が徐々に増加していきます。

無限集合に関連する計算可能性に関する結果には、多くの場合、命名法が関係します。命名法とは、それらの集合と、その部分集合の再帰的表現との間の写像です。集合上の命名法は、その集合上の位相を生み出します。これについては、以下で詳しく説明します。

タイプ1の計算可能性とは、計算可能な解析の素朴な形式であり、機械への入力を任意の実数ではなく計算可能な数値に限定するものである。

2つのモデルの違いは、計算可能な数上で適切に振る舞うプログラム（全体的という意味で）が、任意の実数上で必ずしも適切に振る舞うとは限らないという点にある。例えば、計算可能な実数上には、有界な閉区間を非有界な開区間に写像する計算可能な関数が存在する。^{[ 3 ]}これらの関数は、すべての計算可能な関数と同様に、任意の実数に拡張することはできない（部分的なものにしない限り） 。$\displaystyle \mathbb {R} \to \mathbb {R} }$連続関数である場合、極値定理に違反することになります。そのような振る舞いは異常とみなされる可能性があるため、関数は計算可能な実数だけでなく、すべての実数にわたって全関数である場合にのみ全関数とみなされるべきだと主張するのは自然なことです。

チューリングマシンの使用に不満がある場合（低レベルでやや恣意的であるという理由で）、クリーネ・ヴェスリー・トポスと呼ばれる実現可能性トポスがあり、そこでは計算可能解析を構成的解析に還元することができます。この構成的解析には、ビショップ学派だけでなく、ブロワー学派で有効なものすべてが含まれます。^{[ 4 ]}さらに、この構成的解析学派の定理は、すべての実数が計算可能であるとは限らないというもので、これは、計算不可能な数が存在することとは構成的に同値ではありません。したがって、この構成的解析学派は、すべての関数が計算可能であると主張するマルコフの学派などの構成的解析学派と直接矛盾します。最終的に、構成的存在は計算可能性を意味しますが、すべての関数が計算可能であるとは限らないと主張することは実際には問題がなく、むしろ有用であることを示しています。