CSEP 590TU Assignment #3
Autumn 2003

Due: Wednesday, October 22, 2003.

Read chapter 5 of Sipser's text, sections 5.1 and 5.3.

Problems:

  1. Sipser's text page 195, Problem 5.5

  2. Sipser's text page 195, Problem 5.9

  3. 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?

  4. Imagine a variant of the C programming language with only integer variables, but whose integer variables are not limited in size; i.e., they may be much longer than 32 or 64 bits and there is no a priori bound on how large they can be. Prove that given as input a program written using this idealized variant of C it is impossible to tell whether or not the program does a division by 0 when its input is a sequence of ten 1's. (You can use the fact that programs written in this language can simulate arbitrary Turing machines.)

  5. (Bonus) Sipser's text page 170, Problem 4.18

  6. (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?