FOM: recursive definitions

Peter Manolios pete at cs.utexas.edu
Fri Nov 2 22:13:42 EST 2001


I am interested in any references that relate to the following
question:

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
equation.

  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