Abstract:
The halting problem, the most (in)famous undecidable problem, has important applications in theoretical and applied computer science and beyond, hence the interest in its approximate solutions.
A program which eventually stops but does not halt “quickly” stops at a time which is algorithmically compressible. This result was converted into anytime algorithms for the halting problem for which the stopping time (cut-off temporal bound) is very large and, in general, cannot be significantly improved.
In this paper we propose two classes of anytime algorithms for the halting problem, a theoretical one based on probability theory and another, more practical one, based on order statistic. Previous experimental studies for small Turing machines suggest that some anytime algorithms in these classes may be indeed feasible. Extensive experimental work is needed in this direction.