What Percentage of Programs Halt? - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

What Percentage of Programs Halt?

Résumé

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.
Fichier non déposé

Dates et versions

lirmm-01279151 , version 1 (25-02-2016)

Identifiants

Citer

Laurent Bienvenu, Damien Desfontaines, Alexander Shen. What Percentage of Programs Halt?. ICALP: International Colloquium on Automata, Languages and Programming, EATCS, Jul 2015, Kyoto, Japan. pp.219-230, ⟨10.1007/978-3-662-47672-7⟩. ⟨lirmm-01279151⟩
192 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More