CHAPTER 13
OTHER MODELS OF COMPUTATION
CHAPTER SUMMARY
Grammars are examples of the concept of a rewriting system: a set of rules by which a string can be successively rewritten to produce other strings and thereby define languages. This chapter briefly outlines some typical rewriting systems and explores their connection with Turing machines.
Although Turing machines are the most general models of computation we can construct, they are not the only ones. At various times, other models have been proposed, some of which at first glance seemed to be radically different from Turing machines. Eventually, however, all the models were found to be equivalent. Much of the pioneering work in this area was done in the period between 1930 and 1940 and ...
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.
