On the Generic Undecidability of the Halting Problem for Normalized Turing Machines | Theory of Computing Systems Skip to main content
Springer Nature Link
Log in

On the Generic Undecidability of the Halting Problem for Normalized Turing Machines

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

Hamkins and Miasnikov presented in (Notre Dame J. Formal Logic 47(4), 515–524, 2006) a generic algorithm deciding the classical Halting Problem for Turing machines with one-way tape on a set of asymptotic probability one (on a so-called generic set). Rybalov (Theor. Comput. Sci. 377, 268–270, 2007) showed that there is no generic algorithm deciding this problem on strongly generic sets of inputs (some subclass of generic sets). In this paper we prove that there is no generic algorithm deciding the Halting Problem for normalized Turing machines on generic sets of inputs. Normalized Turing machines have programs with the following natural restriction: internal states with large indices are not allowed at the beginning of the program. This condition does not reduce the class of computable functions because for every Turing machine there exists a normalized Turing machine which computes the same function. Our proof holds for machines with one-way and two-way tape. It also implies that the Hamkins-Miasnikov algorithm is not generic for normalized Turing machines.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Calude, C.S., Stay, M.A.: Most programs stop quickly or never halt. Adv. Appl. Math. 40(3), 295–308 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  2. Chaitin, G.J.: A theory of program size formally identical to information theory. J. ACM 22, 329–340 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  3. Hamkins, J.D., Miasnikov, A.: The halting problem is decidable on a set of asymptotic probability one. Notre Dame J. Formal Logic 47(4), 515–524 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Kapovich, I., Myasnikov, A., Schupp, P., Shpilrain, V.: Generic-case complexity, decision problems in group theory and random walks. J. Algebra 264(2), 665–694 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  5. Rybalov, A.: On the strongly generic undecidability of the Halting Problem. Theor. Comput. Sci. 377, 268–270 (2007)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

Supported by Russian Science Foundation, grant 14-11-00085

Author information

Authors and Affiliations

  1. Omsk State Technical University, prospekt Mira 11, Omsk, 644050, Russia

    Alexander Rybalov

Authors
  1. Alexander Rybalov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexander Rybalov.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Rybalov, A. On the Generic Undecidability of the Halting Problem for Normalized Turing Machines. Theory Comput Syst 60, 671–676 (2017). https://doi.org/10.1007/s00224-016-9698-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-016-9698-9

Keywords

Search

Navigation