実務プログラマーのための Primitive Recursive Functions

原始再帰関数: 実務プログラマーのためのガイド

プログラマーはしばしば「チューリング完全性」という用語を使う。特定のドメインでは、チューリング完全でないことが美点や要件と見なされることもある。しかし、ほとんどの議論は誤った情報に基づいている。チューリング完全でないことが実際に意味するものは別にある。チューリング完全性は数学用語であり、非常に具体的な意味を持つ。これを別の用途向けに再解釈することはできない。

Part I: 要約

• チューリング完全な言語で書かれたプログラムが O(22N) より速く実行されるなら、チューリング完全でない言語でも実装できる。
• ほとんどの実用的な問題は「2の2の2」より速い。
• チューリング完全でない言語は、実用上ほとんど制約にならない。
• プログラムが停止しない場合と、停止に途方もない時間がかかる場合は、同じものとして扱われる。

Part II: 機械の動作原理

有限状態機械 (Finite State Machines)

• 有限状態機械は文字列を入力として受け取り、「はい」または「いいえ」を返す。
• 有限個の状態を持つ。
• 状態遷移関数は現在の状態と次の入力記号を受け取り、新しい状態を返す。
• 有限状態機械は無限ループに入ることができない。
• 有限状態機械は正規表現と同等の表現力を持つ。

チューリング機械 (Turing Machines)

• チューリング機械は有限状態機械より少し複雑である。
• チューリング機械は可変長のテープを使って動作する。
• 状態遷移関数は現在の状態とテープ上の現在の記号を受け取り、新しい状態、記号、移動方向を返す。
• チューリング機械は関数として動作し、無限ループに入ることがある。
• チューリング機械は有限状態機械をシミュレートできる。

チューリング機械のプログラミング

• チューリング機械は無限のテープを持つ。
• チューリング機械はユーザー提供のプログラムを実行しない。プログラムは機械にハードコードされている。
• 万能チューリング機械は他のチューリング機械をシミュレートできる。
• チューリング機械は Python のような言語と同等の計算能力を持つ。

チューリング機械の限界

• チューリング機械で実装できない関数が存在する。
• すべてのチューリング機械を列挙することはできるが、すべての関数を列挙することはできない。
• 特定の問題（例: 停止性問題）はチューリング機械では解けない。
• チューリング機械の強力さは、プログラムが停止するかどうかを判定できなくする。

Part III: 実用的な問題に戻る

原始再帰関数 (Primitive Recursive Functions)

• 原始再帰関数は自然数のタプルを入力として受け取り、自然数を返す関数である。
• zero と succ 関数から始めて、他の関数を構成する。
• 一般的な再帰は許されないが、制限された形のループは許される。
• 加算、乗算、累乗などの演算を定義できる。
• 論理演算子と条件分岐を定義できる。
• データ構造を表現するために数を使う。

GN⁺の要約

• この記事は、チューリング完全性と原始再帰関数への理解を助けるために書かれている。
• チューリング完全でないことが実用上どのような意味を持つのかを説明する。
• 有限状態機械とチューリング機械の違いを説明し、チューリング機械の限界を論じる。
• 原始再帰関数の定義と使い方を説明する。
• この記事は、プログラマーがチューリング完全性と原始再帰関数への理解を深める助けになるだろう。
• 類似の機能を持つものとして「正規表現」と「有限状態機械」がある。