Computable functions of reals

MaRDI QIDQ3003945zbMATH OpenFDO

Authors Katrin Tent, Martin Ziegler

Publication date 31 May 2011

Full work available at URL https://arxiv.org/abs/0903.1384

zbMATH Keywords

computable function of realscomputable real numberelementary functionsGrzegorczyk hierarchylower elementary functionsYoshinaga's theorem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computation over the reals, computable analysis (03D78) Constructive and recursive analysis (03F60)

Abstract: We introduce a new notion of computable function on $R^N$ and prove some basic properties. We give two applications, first a short proof of Yoshinaga's theorem that periods are el (they are actually low). We also show that the low complex numbers form a algebraically closed field closed under exponentiation and some other special functions.

Recommendations

• Computability of Real Numbers by Using a Given Class of Functions in the Set of the Natural Numbers
• Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions
• Basic properties of computable numbers
• Automata, Languages and Programming
• On the Definition of Computable Function of a Real Variable

Cited in

(21)

• Analog computers and recursive functions over the reals.
• Real number computability and domain theory
• Representations of natural numbers and computability of various functions
• Models of computation for partial functions on the reals
• Spectrum of the field of computable real numbers
• Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions
• On a relative computability notion for real functions
• Relativization of Real Numbers to a Universe
• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 1088270 (Why is no real title available?)
• Computability of Real Numbers by Using a Given Class of Functions in the Set of the Natural Numbers
• Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
• Computability and the Implicit Function Theorem
• scientific article; zbMATH DE number 1421076 (Why is no real title available?)
• scientific article; zbMATH DE number 7360045 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• Relatively computable functions of real variables
• Elementarily traceable irrational numbers
• Periods, power series, and integrated algebraic numbers
• The elementary computable functions over the real numbers: applying two new techniques
• Computability on reals, infinite limits and differential equations

This page was built for publication: Computable functions of reals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3003945)