Advice on the Writing Projects for Chapter 10

1. See the chapter on generative grammars in [De2]. Lindenmeyer systems are a special kind of generative grammar.

2. Most textbooks on programming languages should discuss this, as well as books on the specific languages mentioned. The call number for programming languages is QA 76.7. As usual, you can find Web sites with this information using a search engine (such as Metacrawler). We turned up this one, with a search for the three keywords "backus," "naur," and "java."

3. One book on computer network protocols that discusses finite state machines is [Ho3].

4. There are several textbooks on automata theory and finite-state machines of all kinds that cover topics such as this. Try [Br1], [Co], [DeDe], [HoUl], or [LePa], for example. These are also good sources for supplementing the material in this chapter. This subject in general (including grammars and formal languages, Turing machines, computability, and computational complexity) is usually called "the theory of computation," and, again, there are numerous books with essentially this title. Amazon.com shows over 100 books in the Theory of Computing subject. See [Si] for a fairly recent and readable one that takes you from the beginning to a fairly advanced level. Two other recent texts in this area are [Sa2] and [Ta].

5. There are entire books on the subject of cellular automata (see [PrDu], for instance). The Game of Life was invented by the British mathematician John H. Conway, and was the subject of several articles in Martin Gardner's Scientific American column during the 1970s. Three of them are collected in [Ga2], which also mentions other books and articles. See also [BeCo], which covers lots of solitaire and two-person games, as well as Life.

6. See standard references on automata theory, such as those mentioned in Writing Project 4. A Web search for the phrase "pushdown automata" should prove useful, too.

7. See standard references on automata theory, such as those mentioned in Writing Project 4. A Web search for the phrase "linear bounded automata" should prove useful, too.

8. Turing's first article is [Tu2], and it is actually quite readable. Keep in mind as you read it that real computers had not yet been invented! You should be able to find demonstration applets of Turing machines on the Web; we liked this one.

9. See standard references on automata theory, such as those mentioned in Writing Project 4. A Web search for the phrase "universal Turing machine" should prove useful, too.

10. This actually opens up the door to most of the important modern-day research in theoretical computer science. For an elementary, nontechnical account, see [Gr2]. See the references given in Writing Project 4 for more details. The big question is whether deterministic Turing machines can compute functions as efficiently as nondeterministic ones. You should definitely consult [GaJo], the classic work in this area. A Web search for the phrase "nondeterministic Turing machine" should prove useful, too.

11. See the references given for Writing Project 10.

12. See standard references on automata theory, such as those mentioned in Writing Project 4.

13. Searching under "lambda calculus" or "recursive function theory" in your library should turn up a place to start. We found some useful information when searching the Web for the phrase "lambda calculus."

14. See standard references on automata theory, such as those mentioned in Writing Project 4.

15. See standard references on automata theory, such as those mentioned in Writing Project 4.