On non-determinancy in simple computing devices | Acta Informatica Skip to main content
Springer Nature Link
Log in

On non-determinancy in simple computing devices

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

This paper studies one-tape Turing machines with k read-only heads which are restricted to the original input. The main result shows that if any set accepted by such a 3-head non-deterministic Turing machine can be accepted by a deterministic Turing machine with more read-only heads, then the deterministic and non-deterministic context-sensitive languages are identical. Several related results are derived and some tantalizing open problems are discussed.

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. Ginsburg, S.: The mathematical theory of context-free languages. New York: McGraw-Hill 1966.

    Google Scholar 

  2. Hopcroft, J. E., Ullman, J. D.: Formal languages and their relation to automata. Addison-Wesley, Reading, Mass., 1969.

    Google Scholar 

  3. Savitch, W. J.: Nondederministic tape-bounded Turing machines: Doctorial thesis, Univ. of Calif., Berkeley, Calif., 1969.

    Google Scholar 

  4. Hartmanis, J., Lewis II, P. M., Stearns, R. E.: Hierarchies of memory limited computations. IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan, p. 179–190, 1965.

  5. Hennie, F. C., Stearns, R. E.: Two-tape simulation of multi-tape Turing machines. JACM 13, 533–546 (1966).

    Google Scholar 

  6. Rabin, M. O.: Real time computation. Israel J. Math. 1, 203–211 (1964).

    Google Scholar 

  7. Hartmanis, J., Hopcroft, J. E.: An overview of the theory of computational complexity. JACM 18, 444–475 (1971).

    Google Scholar 

  8. Hartmanis, J., Stearns, R. E.: On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 285–306 (1965).

    Google Scholar 

  9. Hartmanis, J.: Computational complexity of random access stored program machines. J. Math. Systems Theory 5, 232–245 (1971).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Gesellschaft für Mathematik und Datenverarbeitung mbH Bonn, Postfach 1240, D-5205, St. Augustin, Schloß Birlinghoven, Federal Republic of Germany

    Juris Hartmanis

Authors
  1. Juris Hartmanis
    View author publications

    You can also search for this author inPubMed Google Scholar

Additional information

This research has been supported in part by National Science Foundation Grant GJ-155.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hartmanis, J. On non-determinancy in simple computing devices. Acta Informatica 1, 336–344 (1972). https://doi.org/10.1007/BF00289513

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00289513

Keywords