# FOM: Re: recursive definitions

Hrant Marandjian hrantm at mosaic.am
Mon Nov 5 10:22:24 EST 2001

```Dear Peter,

Let us specify first what means the term "recursive equation"
satisfable by a total (recursive) function f.
For example, it may be specified as follows:
Given two recursive functionals F and G does it
exist a (recursive) total function f such that F(f)=G(f).
If you mean this case then the complexity of  total recursive
solution existence is \Sigma_3^0 - complete.
If we drop the requirement of computability  of  f  then the
complexity of  solution existence is \Sigma_1^1-complete.
As we see, in each of these cases conditions for a solution
to be total are not "tangible".

Details can be found in:
H. B. Marandjian, General Form Recursive Equations 1,
Computer Science Logic, Lecture Notes in Compututer  Science,
vol. 933, Berlin Heidelberg, Springer, 1995, pp. 501--511.

Hrant Marandjian
hrantm at mosaic.am

----- Original Message -----
From: "Peter Manolios" <pete at cs.utexas.edu>
To: <fom at math.psu.edu>
Sent: Saturday, November 03, 2001 7:13 AM
Subject: FOM: recursive definitions

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

```