The halting problem is decidable on a set of asymptotic probability one

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The halting problem for Turing machines is decidable on a set of asymptotic probability one. Specifically, there is a set B of Turing machine programs such that (i) B has asymptotic probability one, so that as the number of states n increases, the proportion of all n-state programs that are in B goes to one; (ii) B is polynomial time decidable; and (iii) the halting problem H intersect B is polynomial time decidable. The proof is sensitive to the particular computational model.
10 pages

Keywords

Logic, 03D10; 68Q17

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/74931

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0504351
 http://arxiv.org/abs/math/0504351

Collections

arXiv