部分再帰関数

部分関数 $g:\mathbb{N}^{n+1}\rightharpoonup\mathbb{N}$ に対して、最小化 $f=\mu g$ を

で定める。右辺は「$g(\vec{x},0),\ldots,g(\vec{x},y-1)$ がすべて定義されて $0$ でなく、$g(\vec{x},y)=0$ となる最小の $y$」であり、そのような $y$ がなければ未定義とする。

部分再帰関数（$\mu$ 再帰関数）とは、基本関数から合成・原始再帰・最小化を有限回用いて得られる部分関数である。ここで合成と原始再帰は、部分関数に対しても同じ式で、$\simeq$ の意味（右辺の各部分が定義されている限りで定義される）で適用する。たとえば $f(\vec{x},y+1)\simeq h(\vec{x},y,f(\vec{x},y))$ では、$f(\vec{x},y)$ が未定義なら $f(\vec{x},y+1)$ も未定義とする。全関数であるものを再帰関数という。