Информационная система "Конференции"

Abstracts

Computability theory

We consider computational model over arbitrary algebraic structure by means of machines over the list superstructure [1]. Such a machine is a generalization of the Blum-Shub-Smale machine for fields and rings introduced in [2]. Using this abstract computational device one can define notions of computable function, computable and computably enumerable set over a structure A. It was obtained in [1] that class of computably enumerable sets can be described with the help of logical language Lcd (the language of computable disjunctions). This logic includes usual first order logic and allows countable disjuctions of computably enumerable sets of formulas. It was also proved that for any algebraic structure A a graph of computable over A function is computably enumerable over A. This statement cannot be inverted for arbitrary structure, for instance, it is easy to construct contrexample for a field of the real numbers [1].

The main result of this report: for arbitrary algebraic structure A it is obtained complete description of those computably enumerable over A sets which are the graphs of computable functions. This description is given in terms of the language or computable disjunctions.

References.

[1] Ashaev I.V., Belyaev V.Y., Myasnikov A.G. Approaches to the theory of generalized computability // Algebra i Logika. -- 1993. - V.32, 4. - P.349-386.

[2] Blum L., Shub M., Smale S. On a theory of computation and complexity over the reals: NP-completeness, recursive function and universal machines // Bull. Amer. Math. Soc., (N.S.), 1989, vol. 21, num. 1, pages 1-46.

Mail to Webmaster alc9@math.nsc.ru

|Home Page| |English Part|

Go to Home