Generic algorithms for halting problem and optimal machines revisited

DOI10.2168/LMCS-12(2:1)2016zbMATH Open1448.03027arXiv1505.00731OpenAlexW3101918022WikidataQ57349380 ScholiaQ57349380MaRDI QIDQ2800974FDOQ2800974

Authors: Laurent Bienvenu, Damien Desfontaines, A. Shen 

Publication date: 19 April 2016

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: The halting problem is undecidable --- but can it be solved for "most" inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered in algorithmic information theory) using the notion of Kolmogorov complexity. We also consider some related questions about this framework and about asymptotic properties of the halting problem. In particular, we show that the fraction of terminating programs cannot have a limit, and all limit points are Martin-L"of random reals. We then consider mass problems of finding an approximate solution of halting problem and probabilistic algorithms for them, proving both positive and negative results. We consider the fraction of terminating programs that require a long time for termination, and describe this fraction using the busy beaver function. We also consider approximate versions of separation problems, and revisit Schnorr's results about optimal numberings showing how they can be generalized.

Full work available at URL: https://arxiv.org/abs/1505.00731

Recommendations

• What percentage of programs halt?
• A probabilistic anytime algorithm for the halting problem
• Fundamentals of Computation Theory
• The halting problem is decidable on a set of asymptotic probability one
• On the strongly generic undecidability of the halting problem

zbMATH Keywords

Kolmogorov complexityhalting problemgeneric algorithmsoptimal enumerations

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10)

Cited In (9)

• A probabilistic anytime algorithm for the halting problem
• Asymptotic proportion of hard instances of the halting problem
• The halting problem is decidable on a set of asymptotic probability one
• What percentage of programs halt?
• A statistical anytime algorithm for the halting problem
• Fundamentals of Computation Theory
• Asymptotic behavior and halting probability of Turing machines
• On the generic undecidability of the halting problem for normalized Turing machines
• THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS

This page was built for publication: Generic algorithms for halting problem and optimal machines revisited

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