Generic algorithms for halting problem and optimal machines revisited

Laurent Bienvenu 1 Damien Desfontaines 2 Alexander Shen 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Article dans une revue
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2016, Logical Methods in Computer Science, 12 (2), pp.1-29. 〈http://www.lmcs-online.org/〉. 〈10.2168/LMCS-12(2:1)2016〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01486494
Contributeur : Alexander Shen <>
Soumis le : jeudi 9 mars 2017 - 21:01:05
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

Collections

Citation

Laurent Bienvenu, Damien Desfontaines, Alexander Shen. Generic algorithms for halting problem and optimal machines revisited. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2016, Logical Methods in Computer Science, 12 (2), pp.1-29. 〈http://www.lmcs-online.org/〉. 〈10.2168/LMCS-12(2:1)2016〉. 〈lirmm-01486494〉

Partager

Métriques

Consultations de la notice

259