A statistical anytime algorithm for the halting problem

DOI10.3233/COM-190250zbMATH Open1485.68119OpenAlexW2910610446MaRDI QIDQ5131647FDOQ5131647

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

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

zbMATH Keywords

order statisticshalting problemrunning timeanytime algorithm

Mathematics Subject Classification ID

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

Cited In (10)

• A probabilistic anytime algorithm for the halting problem
• Asymptotic proportion of hard instances of the halting problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Universal halting times in optimization and machine learning
• Promise problems on probability distributions
• Computable model discovery and high-level-programming approximations to algorithmic complexity
• Title not available (Why is that?)
• Asymptotic behavior and halting probability of Turing machines
• Halting time is predictable for large models: a universality property and average-case analysis

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)