再帰関数とレジスタマシン

再帰関数理論は、いくつかの基本的な操作から計算可能関数を構築する。一方、レジスタマシンは、レジスタに格納された整数を用いて計算を行う。これら2つのモデルはチューリングマシンを挟み込み、計算可能性の堅牢性を裏付けている。

Definition

一般再帰関数とは、定数、後者関数、射影関数から、合成、原始再帰、非有界最小化によって構築される関数である。レジスタマシンとは、自然数を保持する有限個のレジスタの内容を増減させたりテストしたりすることによって計算を行う抽象的な装置である。

Scope

このトピックでは、原始再帰関数、一般再帰関数を得るための非有界最小化の追加、原始再帰的ではない計算可能関数としてのアッカーマン関数、レジスタマシンとカウンタマシンおよびそれらの普遍性、そしてこれらすべてのモデルとチューリング計算可能性との等価性について扱う。

Core questions

• 計算可能関数は、いかなる機械も用いずに算術的にどのように定義できるか？
• 原始再帰を超えて非有界最小化が必要なのはなぜか？
• 単純なレジスタマシンはどのようにして計算の全能力を達成するのか？
• これらの算術モデルと機械モデルがチューリングマシンと一致するのはなぜか？

Key theories

チューリング計算可能性との等価性

一般再帰関数とレジスタマシンによって計算される関数は、正確にチューリング計算可能関数であり、純粋に算術的および初等的な機械の観点から定義されたモデルを通じて、チャーチ＝チューリングの提唱を補強する。

原始再帰を超えて

アッカーマン関数は全域かつ計算可能であるが、原始再帰的であるには成長が速すぎる。これは、非有界探索が不可欠であり、原始再帰関数が計算可能関数の真のサブクラスであることを示している。

レジスタマシンの普遍性

ミンスキーは、インクリメント、デクリメント、ゼロテストの操作のみを持つ2つのカウンタを持つマシンがすでにチューリング完全であることを示した。これは、完全な計算にどれほど少ない構造しか必要としないかを示す極端な例である。

Clinical relevance

レジスタマシンは、テープよりも直接的に実際のプロセッサの整数演算をモデル化する。原始再帰は常に終了するプログラムに対応し、全域関数型言語と終了解析の基礎となる。また、再帰関数の視点は、計算を数学の基礎と結びつける。

History

ゲーデルとヘルブランは1930年代初頭に一般再帰関数を定義し、クリーネは最小化の役割を含む理論を発展させた。アッカーマンはそれ以前に彼の急成長関数を示しており、ミンスキーは1960年代にレジスタマシンとカウンタマシンを導入し、2カウンタマシンでさえ普遍的であることを証明した。

Key figures

• Kurt Gödel
• Stephen Kleene
• Wilhelm Ackermann
• Marvin Minsky

Seminal works

• cutland1980
• minsky1967

Frequently asked questions

原始再帰関数と一般再帰関数の違いは何ですか？

原始再帰関数は有界ループを用いて構築され、常に終了しますが、すべての計算可能関数を捉えるわけではありません。無期限に実行される可能性のある探索である非有界最小化を追加すると、一般再帰関数が得られ、これはチューリング計算可能関数と正確に一致します。

たった2つのカウンタを持つ機械が、どのようにしてコンピュータと同じくらい強力になり得るのですか？

ミンスキーは、自然数を保持する2つのレジスタが、インクリメント、デクリメント、ゼロテストの操作のみで、そのテープをレジスタにエンコードすることでチューリングマシンをシミュレートできることを示しました。この構成は非常に非効率的ですが、最小限のハードウェアでも計算の全能力に到達することを証明しています。