Effective simultaneous approximability of reals.

DOI10.1016/S0304-3975(01)00097-4MaRDI QIDQ1607296zbMATH OpenFDO

Authors Vladimir Nikolaevich Krupskiĭ

Publication date 31 July 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00097-4

zbMATH Keywords

ComputabilityDiophantine approximation problemHierarchyKolmogorov complexityScale

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

The effective simultaneous approximability of real vectors and sets of reals is studied. A hierarchy of real vectors based on the Kolmogorov complexity of computable approximations is constructed. We prove that the hierarchy is nontrivial at the bottom levels but collapses on the top levels. A hierarchy theorem which gives a simple test for proper inclusion between two classes is established. We also show that an effective approximation problem for a finite set may be hard (have no computable solutions) when the corresponding problems for all its proper subsets are simple (have computable solutions).

Recommendations

• Classification of computably approximable real numbers
• The approximation structure of a computably approximable real
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Approximation representations for reals and their wtt‐degrees
• On the hierarchy and extension of monotonically computable real numbers.

Cites work

• Diophantine approximation
• scientific article; zbMATH DE number 4133978 (Why is no real title available?)
• scientific article; zbMATH DE number 3831924 (Why is no real title available?)
• scientific article; zbMATH DE number 4070894 (Why is no real title available?)
• scientific article; zbMATH DE number 3730117 (Why is no real title available?)
• scientific article; zbMATH DE number 42077 (Why is no real title available?)
• scientific article; zbMATH DE number 107775 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Recursive analysis

Cited in

(3)

• scientific article; zbMATH DE number 5570799 (Why is no real title available?)
• The approximation structure of a computably approximable real
• Effective infinitesimals in \(\mathbb{R}\)

This page was built for publication: Effective simultaneous approximability of reals.

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