PR (計算複雑性理論)

計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。
原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。
PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である（チューリングマシンの停止問題が決定不能であるため）。すなわち、PR は構文的クラスであり、R は意味論的クラスである。
一方、任意の帰納的可算集合（REも参照）を原始再帰関数を次のように使って枚挙可能である。入力 ("M", "k") を与えたとき（"M" はチューリングマシン、"k" は整数）、"M" が "k" ステップ以内に停止するなら "M" を出力するものとする。そうでない場合は何も出力しない。すると ("M", "k") の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する "M" の集合に他ならない。