# 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:

- 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
of L(N)?
- 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
machines.)
- (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?