Abstract:
A program which eventually stops but does not halt “too quickly” halts at a time which
is algorithmically compressible. This result—originally proved in [4]—is proved in a more
general setting. Following Manin [11] we convert the result into an anytime algorithm
for the halting problem and we show that the stopping time (cut-o! temporal bound)
cannot be significantly improved.