Partial Recursive Functions

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.