CMPS 210 Homework 4, Winter 2002  

3 problems assigned Jan. 31, due Feb. 7. 
Work in groups of up to three, with one solution submitted for each group
with the names of all group members on the solutions.

1) Prove that for all Languages L, L is recognized by the kind of 
Turing Machine presented in class (with a 1-way infinite tape)
if and only if L is recognized by the kind of Turing Machine
presented in the book.  (In the book's style, a string is 
accepted by a TM if the TM halts with just a "yes" character (say 1)
on the tape and rejects a string if it halts with just a "no" character
(say 0) on the tape (the remainder of the tape is all blanks).

2) Exercise 4.5 on page 111 of the text.  You can use the subroutines
in Figure 4.6 and/or can create more of your own. 

3) Exercise 4.8 on page 117 of the text.