Anytime Algorithms for Non-Ending Computations
Cristian S. Calude, Damien Desfontaines · International Journal of Foundations of Computer Science · 2015
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-off temporal bound) cannot be significantly improved.