CSE 531 Assignment #3
Autumn 1999

Due: Tuesday, November 9, 1999.

Problems from Sipser's text:

  1. page 195, Problem 5.5

  2. page 195, Problem 5.7

  3. page 195, Problem 5.9

  4. page 195, Problem 5.13

  5. page 195, Problem 5.14

  6. page 196, Problem 5.20

  7. page 196, Problem 5.22

  8. Which of the following are decidable? Prove your answers.

    1. Given a Turing machine M, string x, and integers a and b does M run for more than a|x|2+b steps on input x?

    2. Given a Turing machine M and integers a and b, does there exist a string x such that M runs for more than a|x|2+b steps on input x?