On Kolmogorov complexity in the real Turing machine setting

DOI10.1016/S0020-0190(98)00089-1MaRDI QIDQ293323zbMATH OpenFDO

Authors J. L. Montaña, Luis Miguel Pardo

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098000891?np=y

zbMATH Keywords

Kolmogorov complexityalgebaric complexity theoryreal computationreal Turing machinesstraight-line complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10)

Recommendations

• Kolmogorov Complexity Theory over the Reals
• The Kolmogorov complexity of random reals
• On the Kolmogorov complexity of continuous real functions
• On the Kolmogorov complexity of continuous real functions
• Kolmogorov-Complexity Based on Infinite Computations

Cites work

• scientific article; zbMATH DE number 3162280 (Why is no real title available?)
• scientific article; zbMATH DE number 4170851 (Why is no real title available?)
• scientific article; zbMATH DE number 4112009 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1057737 (Why is no real title available?)
• scientific article; zbMATH DE number 1096865 (Why is no real title available?)
• scientific article; zbMATH DE number 1142293 (Why is no real title available?)
• scientific article; zbMATH DE number 3058859 (Why is no real title available?)
• Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
• Lower bounds for polynomials with algebraic coefficients
• Lower bounds in algebraic computational complexity
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the intrinsic complexity of elimination theory
• Polynomials with Rational Coefficients Which are Hard to Compute
• Some polynomials that are hard to compute

Cited in

(12)

• New Computational Paradigms
• scientific article; zbMATH DE number 4008382 (Why is no real title available?)
• Kolmogorov complexity for possibly infinite computations
• scientific article; zbMATH DE number 1390092 (Why is no real title available?)
• Reconciling Data Compression and Kolmogorov Complexity
• On the Kolmogorov complexity of continuous real functions
• On the Kolmogorov complexity of continuous real functions
• Kolmogorov complexity and characteristic constants of formal theories of arithmetic
• The Kolmogorov complexity of real numbers.
• Smale's 17th problem: average polynomial time to compute affine and projective solutions
• Kolmogorov Complexity Theory over the Reals
• scientific article; zbMATH DE number 3924764 (Why is no real title available?)

This page was built for publication: On Kolmogorov complexity in the real Turing machine setting

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