CHAPTER 9
TURING MACHINES
CHAPTER SUMMARY
Here we introduce the important concept of a Turing machine, a finite-state control unit to which is attached a one-dimensional, unbounded tape. Even though a Turing machine is still a very simple structure, it turns out to be very powerful and lets us solve many problems that cannot be solved with a pushdown automaton. This leads to Turing’s Thesis, which claims that Turing machines are the most general types of automata, in principle as powerful as any computer.
In our discussion so far we have encountered some fundamental ideas, in particular the concepts of regular and context-free languages and their association with finite automata and pushdown accepters. Our study has revealed that the regular ...
Get An Introduction to Formal Languages and Automata, 6th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
