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

Simple item page
dc.creatorHamkins, Joel David
dc.creatorMiasnikov, Alexei
dc.date2005-04-18
dc.date.accessioned2026-07-07T05:19:11Z
dc.date.available2026-07-07T05:19:11Z
dc.descriptionThe 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.
dc.description10 pages
dc.identifierhttps://arxiv.org/abs/math/0504351
dc.identifierhttp://arxiv.org/abs/math/0504351
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/74931
dc.subjectLogic
dc.subject03D10; 68Q17
dc.titleThe halting problem is decidable on a set of asymptotic probability one
dc.typetext

Files

Collections

arXiv