Partial recursive functions are particular functions from some subset of vectors of
NaturalNumbers to
NaturalNumbers. A partial recursive function may be undefined (divergent) at some points.
Every
PrimitiveRecursiveFunction is a partial recursive function
Also if
f(
x,
y1,...,
yn) is a partial recursive function of
n+1 variables then (µ
f)(
y1,...,
yn) is a partial recursive function of
n variables.
The µ operator
The µ operator performs an unbounded search on
f.
(µ
f)(
y1,...
yn) is the least
x such that
f(
x,
y1,...,
yn)=0, or diverges if none exists. Also if there is a y < x such that
f(
y,
y1,...,
yn) diverges then (µ
f)(
y1,...
yn) also diverges.
The idea is that the computation keeps trying values for x in increasing order until a value for
f(
x,
y1,...,
yn) is found to be 0. Therefore if some previous value for
f diverges (think of diverging as stuck in an infinite loop) then the search also diverges.
PartialRecursiveFunctions provide a simple
ModelOfComputation.