A probabilistic anytime algorithm for the halting problem

Issue title: In Memory of S. Barry Cooper (1943–2015)

Guest editors: Benedikt Löwe

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

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. Experimental results reported on various models of computation suggest that halting programs are not uniformly distributed – running times play an important role. A reason is that a program which eventually stops but does not halt “quickly”, stops at a time which is algorithmically compressible. In this paper we work with running times to define a class of computable probability distributions on the set of halting programs in order to construct an anytime algorithm for the Halting problem with a probabilistic evaluation of the error of the decision.

Keywords: Halting Problem, anytime algorithm, running time distribution

DOI: 10.3233/COM-170073

Journal: Computability, vol. 7, no. 2-3, pp. 259-271, 2018