巨大数研究 Wiki
Advertisement

計算とは

まず数学の対象として扱えるようにするために、「計算」に関するもろもろのイメージを適当な形式で表したい。

「計算」という言葉の意味は図り難く、物理と違って実在に気を遣う必要もないため、ひとまずたかだか可算無限種類の状況のたかだか可算無限長の列で表されるもので考えるものとする。停止状況なるものから先は無視することで停止とみなす。

概要を述べると、適当なメタ理論MTから言語Lを定義し、L-理論T^Lを定義し、T^L上でその計算機がなりうる状況とその遷移列を表すことができるΔ_1な遷移関数δを定義してこれをL-計算機モデルとみなす。定義可能性はメタ理論MTによる。

T^L上でその計算機が扱うことができるコード化されたLに相当する言語[L]を定義し、その計算機にある範囲で値を決定可能な関数型[L]-論理式[φ]とこれに与えるコード化された引数とこの値を決定できるほど十分強い、[L]-理論[T]を任意に与えたとき健全な値を返すことができれば

計算を記述する言語

状況を記述する言語と列を生成する遷移関数を記述する言語(関数記号)は別にしてみる。

Advertisement