A probabilistic anytime algorithm for the halting problem

DOI10.3233/COM-170073MaRDI QIDQ4683154zbMATH OpenOpenAlexFDO

Authors Monica Dumitrescu, Cristian S. Calude

Publication date 20 September 2018

Published in Computability (Search for Journal in Brave)

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

zbMATH Keywords

anytime algorithmhalting problemrunning time distribution

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Probability distributions: general theory (60E05) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• A statistical 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
• The halting problem is decidable on a set of asymptotic probability one

Cited in

(17)

• 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
• Generic algorithms for halting problem and optimal machines revisited
• Decision incorporation in meta-heuristics to cope with decision scheduling problems
• A Parameterized Halting Problem
• Asymptotic proportion of hard instances of the halting problem
• Universality in numerical computations with random data
• Promise problems on probability distributions
• scientific article; zbMATH DE number 5506884 (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
• scientific article; zbMATH DE number 2086480 (Why is no real title available?)
• A statistical anytime algorithm for the halting problem
• Superintelligence cannot be contained: lessons from computability theory
• scientific article; zbMATH DE number 5201472 (Why is no real title available?)
• Fundamentals of Computation Theory
• Asymptotic behavior and halting probability of Turing machines

This page was built for publication: A probabilistic 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 Q4683154)