Cellular Automata and \delta-Uniform BSS Machines
by
Adriana Popovici
Department of Mathematics, University of the West Timisoara, B-dul V.Pârvan nr. 4, 1900 Timisoara, ROMANIA
Coauthors: Dan Popovici (Department of Mathematics, University of the West Timisoara, B-dul V.Pârvan nr. 4, 1900 Timisoara, ROMANIA)

Cellular automata represent a well-known model of computation. This paper deals with the notion of \delta- uniform BSS decidability in comparison with the power of acceptance by cellular automata. An important role is played by CA closed fields.

It is emphasized the relationship between \delta-uniform BSS machines introduced by P. Boldi and S. Vigna (\delta-Uniform BSS Machines, Journal of Complexity 14 (1998), 234-256) and k-cellular acceptors. We give also a characterization of the existence of \delta-uniformly decidable sets. More exactly, there is a \delta-uniformly decidable set X included in (0, 1) \cap A iff there is a real \alpha in the complement of A CA over A.

The partially ordered set of CA closed fields is proved isomorphic to the ideal completion of unsolvability degrees. We show that the ideal completion of the partially ordered set of degrees is isomorphic to the set of CA closed subfields of R. A real number f is CA over A iff dg f in [dg A] (the ideal generated by dg A). For each CA closed field A, dg A is an ideal of degrees. For each ideal I, the set dg^-1I={ f in R | dg f in I} is a CA closed field. As a consequence we observe that for an archimedean field A and its CA closure C, [dg A]=dg C. Conclude the paper by proving that the map dg is an isomorphism between the poset of CA closed fields and the poset of ideals.

Date received: February 25, 2000