# CSE 417 Assignment #4

Winter 2000

### Due: Monday, February 28, 2000.

Finish reading the Manber text, Chapter 9, sections 9.1, 9.2, 9.3, 9.4,
and 9.6 on the material we have already covered.
We will not cover pattern matching as planned because of time constraints.
The next topic will be a rough sketch of the definition of Turing machines
and the proof of the unsolvability of the Halting problem. This is covered in
a fair amount of detail in the text by Sipser. We will only be able to skim
the surface. If you have the Sipser text, read the first part of section 3.1
of the Sipser text, keeping to the intuitive part and skipping the formal
details. Then read section 3.3. We will then jump to material in section 4.2
of the Sipser text, on the Halting problem.

- Manber's text: page 257, problem 7.65
- Apply Euclid's algorithm to compute the gcd of 291 and 213.
- Manber's text: page 319, problem 9.18
- Describe at a high level, how you might simulate a Turing machine
in your favorite programming language.
- Let B be the set of all infinite sequences of 0's and 1's.
Show that B is uncountable.
- (Bonus) Manber's text: page 257, problem 7.69