Anytime algorithms for non-ending computations

DOI10.1142/S0129054115500252MaRDI QIDQ2947801zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Damien Desfontaines, Cristian S. Calude

Publication date 29 September 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054115500252

zbMATH Keywords

algorithmically compressible numberanytime algorithmdensityhalting problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3997169
• Kolmogorov complexity for possibly infinite computations
• Asymptotic behavior and halting probability of Turing machines
• Algorithmic complexity as a criterion of unsolvability
• scientific article; zbMATH DE number 7378319

Cites work

• Most programs stop quickly or never halt
• Natural halting probabilities, partial randomness, and zeta functions
• Renormalisation and computation. II: Time cut-off and the halting problem
• Strong noncomputability of random strings
• The halting problem is decidable on a set of asymptotic probability one

Cited in

(6)

• Renormalisation and computation. II: Time cut-off and the halting problem
• On-the-fly algorithms and sequential machines
• Universal halting times in optimization and machine learning
• A probabilistic anytime algorithm for the halting problem
• A statistical anytime algorithm for the halting problem
• On-the-Fly Algorithms and Sequential Machines

This page was built for publication: Anytime algorithms for non-ending computations

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