2013 May 7,

Carleton College, Spring 2013

Prof. Joshua R. Davis, , CMC 325, x4473

A. Problem 4.18. Hint: Two TMs are "given" to you, albeit only implicitly. Run them in parallel, by interleaving their steps. Then what?

Recall from class: The number of (finite) bit strings is called beth_{0} (also called aleph_{0}). The bit strings can be put into one-to-one correspondence with the natural numbers. The number of (infinite) bit sequences is called beth_{1} (also called C). The bit sequences cannot be put into one-to-one correspondence with the natural numbers. Therefore beth_{0} ≠ beth_{1}.

B. Find a subset *S* of the set of bit sequences, such that there exists a one-to-one correspondence between the set of bit strings and *S*. Describe *S* and the correspondence explicitly.

You have just proved that beth_{0} ≤ beth_{1}. Roughly speaking, because beth_{0} ≠ beth_{1}, we can conclude that beth_{0} < beth_{1}. Then, because the number of Turing machines over Σ = {0, 1} is less than or equal to beth_{0}, and the number of languages over Σ = {0, 1} is beth_{1}, we can conclude that the number of Turing machines is less than the number of languages. By the pigeonhole principle, there must exist a language *A* that is not the language of any Turing machine. In other words, there must exist a language *A* that is not recognizable.