﻿ CS 254: Day 16

2013 May 7,

# CS 254: Day 16

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.