Zentralblatt für Mathematik
Mathematics Abstracts

851.03012

Freund, Rudolf; Staiger, Ludwig:
Numbers defined by Turing machines.
[CA] Collegium logicum. Annals of the Kurt Goedel Society. Volume 2. Wien: Springer-Verlag, 118-137 (1996). [ISBN 3-211-82796-X/pbk]

Classification
*03D10 Turing machines and related notions
12D99 Real and complex fields
11K99 Probabilistic theory
12L99 Connections of field theory with logic
Keywords:
classes of real numbers; classes of complex numbers; algebraically closed fields; Turing machine; mappings over infinite words

The Turing machine considered in this paper has a semi-infinite read only input tape, a semi-infinite output tape and a finite number of working tapes. A deterministic Turing machine is called strict if it never changes a symbol written on its output tape. There are three natural types of Turing machines: nondeterministic, deterministic and strict deterministic.
The authors study characteristic properties of mappings over infinite words defined by these three types of Turing machines. Using the interpretation of infinite words as the expansions of real respectively complex numbers they introduce three classes of real and complex numbers defined by corresponding classes of Turing machines. Some set and arithmetic properties of these number classes are obtained. The main result is the following: the three defined classes of complex numbers form algebraically closed subfields of the field of complex numbers.
A.V. Anisimov (Kiev)

Publ. Year: 1996
Document Type: Journal

(c) 1996 FIZ Karlsruhe & Springer-Verlag