1 Show that the set of all binary languages is uncountable 2

1. Show that the set of all binary languages is uncountable.

2. Show that the set of all Turning Machines is countable.

3. What does this imply about decidability?

Solution

1. first solution: The set of all strings on a a binary alphabet ( ) is countably infinite. We proved this in class, but it’s easy to see if you put the strings in lexicographical order. We can then assign each string to its place in that ordering (i.e. = 1,0 = 2,1 = 3,. . . ) to obtain a bijection with N. The set of all languages is the power set of all strings. The power set of a countably infinite set is uncountably infinite, so the set of all binary languages is uncountably infinite.

1. alternate solution : We prove this by contradiction using the diagonalization method. Assume that we can construct a bijective mapping f : N B, where N are the natural numbers and B is the set of all infinite binary sequences. Then, n f(n) 1 0100111 ... 2 11111000 ... 3 1011001 ... . . . . . . k 0010 ... 0k ... . . . . . . Observe that we can always construct another binary sequence which will differ from all the enumerated sequences by at least one bit, 100 ... 1k ... That is, for any value i we have constructed a sequence which will differ in value from f(i) in the ith bit. Therefore, there exist elements in B that are not in the image of f. That means our assumption that f is bijective is incorrect

2. Solution: Let 0,1 = { 0, 1 } be the alphabet over the symbols 0 and 1, observe that the set of all strings over this alphabet, say 0,1, is countably in finite by the fact that we can interpret each string in this set as the binary encoding of a natural number. Now, let M0,1 be the binary encoding of some Turing machine M. It is clear that such an encoding exists, since any other encoding M can be transformed into the encoding M0,1 by representing each symbol in as a unique string in 0,1. a Now, let M 0,1 be the set of all encoded, valid Turing machine descriptions. Observe that M 0,1 0,1. This implies that the set of all Turing machines is countable in finite.

3. If a language is decidable, then its complement is decidable (by closure under complementation). For the other direction, let L and L be recognizable by M1 and M2, respectively. We construct machine M that decides L: M := “On input w, Set n = 1 1. Simulate M1 on w for n steps. If it accepts, accept 2. Simulate M2 on w for n steps. If it accepts, reject 3. Increment n and go to step 1” Either w L, or w L . Therefore either M1 or M2 will halt in a finite number of steps. Therefore M will halt in a finite number of steps