What Percentage of Programs Halt?

Abstract : Fix an optimal Turing machine U and for each n consider the ratio ρ^U_n of the number of halting programs of length at most n by the total number of such programs. Does this quantity have a limit value? In this paper, we show that it is not the case, and further characterise the reals which can be the limsup of such a sequence ρUn. We also study, for a given optimal machine U, how hard it is to approximate the domain of U from the point of view of coarse and generic computability.
Type de document :
Communication dans un congrès
ICALP: International Colloquium on Automata, Languages and Programming, Jul 2015, Kyoto, Japan. Springer, 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, LNCS (9134), pp.219-230, 2015, Automata, Languages, and Programming. 〈http://link.springer.com/10.1007/978-3-662-47672-7〉. 〈10.1007/978-3-662-47672-7〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01279151
Contributeur : Alexander Shen <>
Soumis le : jeudi 25 février 2016 - 14:51:51
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Identifiants

Collections

Citation

Laurent Bienvenu, Damien Desfontaines, Alexander Shen. What Percentage of Programs Halt?. ICALP: International Colloquium on Automata, Languages and Programming, Jul 2015, Kyoto, Japan. Springer, 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, LNCS (9134), pp.219-230, 2015, Automata, Languages, and Programming. 〈http://link.springer.com/10.1007/978-3-662-47672-7〉. 〈10.1007/978-3-662-47672-7〉. 〈lirmm-01279151〉

Partager

Métriques

Consultations de la notice

149