FOM: recursive definitions

Peter Manolios pete at
Fri Nov 2 22:13:42 EST 2001

I am interested in any references that relate to the following

Under what conditions is a recursive equation satisfiable by some
total function?

Notice, that I am interested in total functions.  If I were interested
in partial functions, then the first recursion theorem from recursive
function theory would be a good reference.  However, that result is
not applicable here.  To see why, consider the following recursive

  f(x) = f(x)+1

The above is "monotone" as per the requirements of the first recusion
theorem, thus, there is a least partial function that satisfies the
equation, namely the nowhere defined function.  However, there are no
total functions which satisfy the above equation.

Any references would be appreciated.  

Pete Manolios

More information about the FOM mailing list