CSE 431 Assignment #4
Spring 2003

Due: Friday, May 2, 2003.

Finish reading chapter 5 of Sipser's text. We will finish sections 5.1 and section 5.2. Skim section 6.2 of the text.

Problems:

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

    1. Given Turing Machine M and state q and input w, does M ever reach q when started on input w?

    2. Given Turing Machine M, does M accept a finite language?

    3. Given Turing machines M and N, is L(M) the complement of L(N)?

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

  2. Show that the following problem about a real programming language is undecidable (if one does not assume a bound on the size of integer variables): Given a program P and a variable v in P, does the execution of P on any input read the value of v before it is initialized?

  3. Page 196, Problem 5.20

  4. (Bonus) page 196, Problem 5.19

  5. (Bonus) Show that the following problem is undecidable. 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?