FOM: recursive definitions
pete at cs.utexas.edu
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
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.
More information about the FOM