A Statistical Anytime Algorithm for the Halting Problem

Abstract

As the Halting Problem, the most (in)famous undecidable problem, has important applications in theoretical and applied computer science and beyond, there is a growing interest in its approximate solutions. Running times play an important role in the study of this problem because halting programs are not uniformly distributed, a fact experimentally confirmed on various models of computation, and a program, which eventually halts but does not halt “quickly”, stops at a time which is algorithmically compressible. In a previous paper we used running times to define a class of computable probability distributions on the set of halting programs and developed a probabilistic anytime algorithm for the Halting Problem. The cut-off temporal bound of this algorithm can be very large. In this paper we propose and study an efficient statistical anytime algorithm for the Halting Problem. The main advantage of the statistical algorithm is that it can be implemented without any prior information about the running times on the specific model of computation and the cutoff temporal bound is reasonable small. The algorithm has two parts: the pre-processing which is done only once (when the parameters of the quality of solutions are fixed) and the main part which us run for any input. With a confidence level as large as required, the algorithm produces correct decisions with a probability as large as required. Three implementations of the algorithm are presented and numerically illustrated. The algorithm can be naturally programmed as a faster hybrid classical-quantum algorithm for classes of instances of the Halting Problem.