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
>
More information about the FOM
mailing list