Anytime Algorithms for Non-Ending Computations

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.