A statistical anytime algorithm for the halting problem

DOI10.3233/COM-190250MaRDI QIDQ5131647zbMATH OpenOpenAlexFDO

Authors Monica Dumitrescu, Cristian S. Calude

Publication date 9 November 2020

Published in Computability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/com-190250

zbMATH Keywords

anytime algorithmhalting problemorder statisticsrunning time

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Order statistics; empirical distribution functions (62G30) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40)

Recommendations

• A probabilistic anytime algorithm for the halting problem
• Anytime algorithms for non-ending computations
• Most programs stop quickly or never halt
• Generic algorithms for halting problem and optimal machines revisited
• Asymptotic behavior and halting probability of Turing machines

Cited in

(11)

• Computable model discovery and high-level-programming approximations to algorithmic complexity
• Halting time is predictable for large models: a universality property and average-case analysis
• Asymptotic proportion of hard instances of the halting problem
• Promise problems on probability distributions
• scientific article; zbMATH DE number 4049059 (Why is no real title available?)
• scientific article; zbMATH DE number 4079400 (Why is no real title available?)
• Universal halting times in optimization and machine learning
• A probabilistic anytime algorithm for the halting problem
• scientific article; zbMATH DE number 5201472 (Why is no real title available?)
• Improved randomized approximation of hard universality and emptiness problems
• Asymptotic behavior and halting probability of Turing machines

This page was built for publication: A statistical anytime algorithm for the halting problem

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