Advertisement
Published in:
2015 | OriginalPaper | Chapter
What Percentage of Programs Halt?
Authors : Laurent Bienvenu, Damien Desfontaines, Alexander Shen
Published in: Automata, Languages, and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Fix an optimal Turing machine
U
and for each
n
consider the ratio
$$\rho ^U_n$$
ρ
n
U
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
$$\rho ^U_n$$
ρ
n
U
. 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.