CMPS 132 HW 5
(1 problem, 5 points, due Tuesday March 7)

Find the two midterm questions on which you were most questionably
graded (either given too many or two few points) and describe why
your score on each problem could have been different.  Include an
exact copy (photocopy encouraged) of your actual midterm answers
to these questions.  (For the purposes of this assignment a "question"
is either a complete problem or  any subproblem worth 4 or more points.)
A solution key to the midterm are in an envelope outside my office.

Reading: Read sections 6.1, 6.2, 7.1, 7.2, and 7.3 in the text.

Optional problems (not to be turned in):
1) Show that PCP remains undecidable even if the alphabet is restricted
to 2 characters.

2) Consider the Language L = {<M,w,h> | h is an accepting computation history of M on input w}.
Is L decidable?