A Real Number Structure that is Effectively Categorical
- 1 January 1999
- journal article
- research article
- Published by Wiley in Mathematical Logic Quarterly
- Vol. 45 (2) , 147-182
Abstract
On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in terms of the theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well‐known non‐appropriateness of the representation to some basebby proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers.Keywords
Funding Information
- DFG Research (HE 2489/2-1)
This publication has 25 references indexed in Scilit:
- Recursive characterization of computable real-valued functions and relationsTheoretical Computer Science, 1996
- Constructive Analysis1985
- Theorie Der Numerierungen IIIMathematical Logic Quarterly, 1977
- Fast Multiple-Precision Evaluation of Elementary FunctionsJournal of the ACM, 1976
- Theorie der Numerierungen IIMathematical Logic Quarterly, 1975
- Theorie der Numerierungen IMathematical Logic Quarterly, 1973
- Signed-Digit Numbe Representations for Fast Parallel ArithmeticIEEE Transactions on Electronic Computers, 1961
- On the definitions of computable real continuous functionsFundamenta Mathematicae, 1957
- Effective procedures in field theoryPhilosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences, 1956
- Computable functionalsFundamenta Mathematicae, 1955