FOM: Re: recursive definitions

[Hrant Marandjian]

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
>