The Halting Problem Is Decidable on a Set of Asymptotic Probability One
Hamkins, Joel David ; Miasnikov, Alexei
Notre Dame J. Formal Logic, Tome 47 (2006) no. 1, p. 515-524 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
The halting problem for Turing machines is decidable on a set of asymptotic probability one. The proof is sensitive to the particular computational models.
Publié le : 2006-10-14
Classification:  Turing machines,  halting problem,  decidability,  03D10,  68Q17 
@article{1168352664,
     author = {Hamkins, Joel David and Miasnikov, Alexei},
     title = {The Halting Problem Is Decidable on a Set of Asymptotic Probability One},
     journal = {Notre Dame J. Formal Logic},
     volume = {47},
     number = {1},
     year = {2006},
     pages = { 515-524},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1168352664}
}

Hamkins, Joel David; Miasnikov, Alexei. The Halting Problem Is Decidable on a Set of Asymptotic Probability One. Notre Dame J. Formal Logic, Tome 47 (2006) no. 1, pp.  515-524. http://gdmltest.u-ga.fr/item/1168352664/