A statistical anytime algorithm for the Halting Problem

Article type: Research Article

Authors: Calude, Cristian S.^{a; *} | Dumitrescu, Monica^b

Affiliations: [a] Department of Computer, Science, University of Auckland, Auckland, New Zealand. cristian@cs.auckland.ac.nz; www.cs.auckland.ac.nz/~cristian | [b] Faculty of Mathematics and Computer Science, Bucharest University, Romania. mdumi@fmi.unibuc.ro; http://goo.gl/txsqpU

Correspondence: [*] Corresponding author. cristian@cs.auckland.ac.nz.

Abstract: In a previous paper we used computer 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 choice of a computable probability distribution – essential for the algorithm – can be rather subjective and hard to substantiate. 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 cut-off temporal bound is reasonably 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 is run for any input program. 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.

Keywords: Halting Problem, anytime algorithm, running time, order statistics

DOI: 10.3233/COM-190250

Journal: Computability, vol. 9, no. 2, pp. 155-166, 2020