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 beth0 (also called aleph0). The bit strings can be put into one-to-one correspondence with the natural numbers. The number of (infinite) bit sequences is called beth1 (also called C). The bit sequences cannot be put into one-to-one correspondence with the natural numbers. Therefore beth0 ≠ beth1.
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 beth0 ≤ beth1. Roughly speaking, because beth0 ≠ beth1, we can conclude that beth0 < beth1. Then, because the number of Turing machines over Σ = {0, 1} is less than or equal to beth0, and the number of languages over Σ = {0, 1} is beth1, 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.