Problem Set Number 9
Computer Science 111

Due by 5 PM, Friday April 21, 2000

In these questions you may represent Turing machines by lists of instructions (like the text) or by state diagrams (the style we use in class).

1. Chapter 10 Exercise 17 (p. 512).

2. Chapter 10 Exercise 23 (p. 512).

3. Chapter 10 Exercise 24 (p. 513). Hint: first go to the rightmost non-blank symbol.