Searching Solutions to General Form Recursive Equations
by
Hrant B. Marandjian
Institute for Informatics and Automation Problems, National Academy of Sciences of Armenia

We consider equation systems of a general form

F1 [f1, f2, ... , fn] = G1 [f1, f2, ... , fn]; ... = ... ; (1) Fk [f1, f2, ... , fn] = Gk [f1, f2, ... , fn] ,

where F_i and G_i are recursive terms representing recursive functionals.

It appears that some of such systems may have computable solutions as well as there are systems that have non-computable solutions at the same time having no computable one (see [1], [2]).

In [1], [2] we have found a condition that is necessary and sufficient for equation system (1) to have a computable solution with respect to f₁, f₂, ... , f_n. We also have shown that for that family of equations the problem of the solution existence in the class of partial recursive (as well as general recursive) functions is a \Sigma₃⁰-complete problem.

Definition. Let t₁, t₂, ... , t_k, be terms representing recursive functionals, and let f₁, f₂, ... , f_n be the list of free function variables occurring in (1). Then we say that

1. t_i [f₁, f₂, ... , f_n] is an i-fragment of < t, f > ;

2. Every term obtained from an i-fragment of < t, f > by replacing some occurrences of f_j(u₁, ... , u_kj), 1 <= j <= n, where u_r's are arbitrary terms, by j-fragments of < t, f > is an i-fragment of < t, f > .

Using the notion of fragment we propose a heuristic method that helps in the search for number-theoretic solutions to equation systems of the above mentioned type.

References

1. H.B. Marandjian, Selected Topics in Recursive Function Theory in Computer Science , DTH, Lyngby, 1990.

2. H.B. Marandjian, General Form Recursive Equations I, in: Computer Science Logic. Selected Papers, Lecture Notes in Computer Science, vol. 933 , Springer, Berlin, Heidelberg, 1995, pp. 501 -511.

Date received: March 15, 2004

Copyright © 2004 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cani-12.