ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Deterministic simulation of non-deterministic turing machines (Detailed Abstract)
Full text PdfPdf (159 KB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the first annual ACM symposium on Theory of computing table of contents
Marina del Rey, California, United States
Pages: 247 - 248  
Year of Publication: 1969
Author
Walter J. Savitch  Department of Mathematics, University of California, Berkeley, California
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 4,   Downloads (12 Months): 30,   Citation Count: 5
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/800169.805439
What is a DOI?

ABSTRACT

Computations of non-deterministic Turing machines are shown to correspond to “solving” certain mazes. The storage needed to “solve” mazes is related to the storage needed to deterministically simulate non-deterministic Turing machines. In particular, it is shown that a non-deterministic L(n)-tape bounded Turing machine can be simulated by an (L(n))2-tape bounded Turing machine, provided L(n)≥log2n.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
P. M. Lewis II, R. E. Stearns, and J. Hartmanis, "Memory Bounds for the Recognition of Context Free and Context Sensitive Languages", IEEE Conference Record on 1965 Symposium on Switching Circuit Theory and Logical Design.
 
2
S. A. Cook and W. J. Savitch, "Mazes and Turing Machines", Technical Report #29, December 1968, Computer Center, University of California, Berkeley.

CITED BY  5
J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971
John T. Gill, III, Computational complexity of probabilistic Turing machines, Proceedings of the sixth annual ACM symposium on Theory of computing, p.91-95, April 30-May 02, 1974, Seattle, Washington, United States
Ronald V. Book , Sheila A. Greibach , Ben Wegbreit, Tape- and time-bounded Turing acceptors and AFLs (Extended Abstract), Proceedings of the second annual ACM symposium on Theory of computing, p.92-99, May 04-06, 1970, Northampton, Massachusetts, United States
Ulla Koppenhagen , Ernst W. Mayr, An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.55-62, July 24-26, 1996, Zurich, Switzerland
Michal Armoni , Mordechai Ben-Ari, The concept of nondeterminism: its development and implications for teaching, ACM SIGCSE Bulletin, v.41 n.2, June 2009

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)


General Terms:
Algorithms, Languages, Measurement, Theory

Collaborative Colleagues:
Walter J. Savitch: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player