CS 3156 Section C, Fall 1998
Homework 7 -- practice only

1. Problem 3.19, page 149 of the text.

2. Prove that the language

displaymath39

is not decidable. (Hint: the idea is similar to the one used for proving that tex2html_wrap_inline51 is not decidable.)

3. Prove that the language

displaymath40

is not decidable. (Hint: the idea is similar to the one used for proving that tex2html_wrap_inline57 is not decidable.)

4. Prove that the language

displaymath41

is not decidable. (Hint: show that tex2html_wrap_inline63 reduces to tex2html_wrap_inline65 . Don't get confused by the fact that tex2html_wrap_inline65 reduces trivially to tex2html_wrap_inline69 , we need the other direction. The idea is to construct for each pair <M,w> a Turing machine that halts on the blank tape if and only if M halts on w. )

5. Prove that the language

displaymath42

is not decidable. (Hint: reduce tex2html_wrap_inline65 to tex2html_wrap_inline84 .)

6. Let tex2html_wrap_inline83 be a fixed Turing machine and tex2html_wrap_inline85 be a fixed string. Is it decidable whether tex2html_wrap_inline87 halts on tex2html_wrap_inline85 or not? Is it decidable whether tex2html_wrap_inline87 always halts? Why or why not? (Hint: think of God.)