CSEP 590TU Assignment #3
Due: Wednesday, October 22, 2003.
Read chapter 5 of Sipser's text, sections 5.1 and 5.3.
- Sipser's text page 195, Problem 5.5
- Sipser's text page 195, Problem 5.9
- Which of the following are decidable? Prove your answers.
- Given Turing Machine M and state q and input w, does M
ever reach q when started on input w?
- Given Turing Machine M, does M accept a finite language?
- Given Turing machines M and N, is L(M) the complement
- 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?
- 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
- (Bonus) Sipser's text page 170, Problem 4.18
- (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?