On Kolmogorov complexity in the real Turing machine setting

DOI10.1016/S0020-0190(98)00089-1zbMATH Open1338.68129MaRDI QIDQ293323FDOQ293323

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

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

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)

Cites Work

• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the intrinsic complexity of elimination theory
• Title not available (Why is that?)
• Lower bounds in algebraic computational complexity
• Some polynomials that are hard to compute
• Lower bounds for polynomials with algebraic coefficients
• Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomials with Rational Coefficients Which are Hard to Compute

Cited In (12)

• Title not available (Why is that?)
• Kolmogorov complexity for possibly infinite computations
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• New Computational Paradigms

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)