CS 3156 Section C, Fall 1998
Homework 6 -- due Wednesday, Nov. 25

1. Problem 3.2(d), page 147 of the text.

2. Give the complete transition table of a Turing machine recognizing the language

displaymath43

Hint: four states (other than tex2html_wrap_inline47 and tex2html_wrap_inline49 ) should suffice.

3. Problem 3.11, page 148 of the text. (Hint: show that any Turing machine with doubly infinite tape is equivalent to a two-tape Turing machine, then use Theorem 3.8 )

4. A Turing machine that halts on all inputs is called halting Turing machine. Prove the following:

(a) If tex2html_wrap_inline51 and tex2html_wrap_inline53 are two halting Turing machines, then there exists a halting Turing machine that recognizes tex2html_wrap_inline55 .
(b) If tex2html_wrap_inline51 and tex2html_wrap_inline53 are two (not necessarily halting) Turing machines, then there exists a Turing machine that recognizes tex2html_wrap_inline55 .

5. An infinite set is called countable if its elements can be placed in a one-to-one and onto correspondence with natural numbers. The set of natural numbers, tex2html_wrap_inline63 , is denoted in the following by tex2html_wrap_inline65 . Which of the following sets are countable? Justify.

(a) The set of all subsets of size 2 of tex2html_wrap_inline65 .
(b) The set of all finite subsets of tex2html_wrap_inline65 .
(c) The set of all sets tex2html_wrap_inline71 , for tex2html_wrap_inline73 .
(d) The set of all subsets of tex2html_wrap_inline65 .

Extra credit. Problem 3.17, page 149 of the text.