Anytime algorithms for non-ending computations

DOI10.1142/S0129054115500252zbMATH Open1338.68127DBLPjournals/ijfcs/CaludeD15OpenAlexW2237358699WikidataQ57001446 ScholiaQ57001446MaRDI QIDQ2947801FDOQ2947801

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

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

zbMATH Keywords

densityhalting problemanytime algorithmalgorithmically compressible number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• A probabilistic anytime algorithm for the halting problem
• Universal halting times in optimization and machine learning
• Renormalisation and computation. II: Time cut-off and the halting problem
• A statistical anytime algorithm for the halting problem
• On-the-fly algorithms and sequential machines
• 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)