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

Joel David Hamkins, Alexei Miasnikov

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

The halting problem for Turing machines is decidable on a set of asymptotic probability one. The proof is sensitive to the particular computational models.

Original languageEnglish
Pages (from-to)515-524
Number of pages10
JournalNotre Dame Journal of Formal Logic
Volume47
Issue number4
DOIs
StatePublished - 2006

Keywords

  • Decidability
  • Halting problem
  • Turing machines

Fingerprint

Dive into the research topics of 'The halting problem is decidable on a set of asymptotic probability one'. Together they form a unique fingerprint.

Cite this