Exercise 1

1. The set S₁ of all the finite strings on {a₁, a₂, ... , a_k} is countable. In fact, we can define a injective function f : S₁ -> N in the following way:

   f(b₁b₂...b_n) = v(b₁)*k^n-1 + v(b₂)*k^n-2 + ... + v(b_n)*k⁰

   where v(a_i) = i. It is easy to see that f is injective (it is similar to the function used to represent numbers in base k; the only difference is that we assign to a_i the value i instead of i-1 in order to count also the prewsence of the initial a₁'s in a string.

   Another injective function g : S₁ -> N which we could have used is

   g(b₁b₂...b_n) = p₁^v(b₁)*p₂^v(b₂)*... *p_n^v(b_n)

   where v(a_i) is defined as before and p_i = i-th prime number.

2. The set S₂ of all the infinite strings on {a₁, a₂, ... , a_k} (for k > 1) is uncountable. The proof is by diagonalization, and it is similar to Cantor's proof that the interval of real numbers between 0 and 1 is not countable (in Cantor's proof the real numbers are represented as infinite strings of digits - the representation of their decimal part).

   Assume (by contradiction) that S₂ is countable. Then consider some indexing of the elemenst of S₂ = {s₁, s₂, ... , s_n, ...}. Define a string s as follows:

   the i-th symbol of s is h(i-th symbol of s_i)

   where h(a₁) = a₂, h(a₂) = a₃, ... h(a_k) = a₁. Since s belongs to S₂, it must have an index (as we are assuming that S₂ is countable). Let j be the index of s, i.e. s = s_j. Let b be the j-th symbol of s_j. Then we have that b = h(b), which is impossible.

3. The set S₃ of all the finite strings on the infinite alphabet {a₁, a₂, ... , a_k, ...} is countable. In fact, S₃ can be obtained as the union of all the sets T_n = set of finite strings on the finite alphabet {a₁, a₂, ... , a_n}. Each T_n is countable (by the part 1 of this exercise), and the set of indexes is N (i.e. n ranges over n). Since N is countable, we have that S₃ is the countable union of countable sets and therefore is countable.

Exercise 2

1. L₁L₂ is RE. The (nondeterministic) TM M which accepts L₁L₂ can be defined in terms of the TMs M₁ and M₂ (accepting L₁ and L₂ respectively) as follows. Let x be the input string. divide nondeterministically x into two substrings x₁ and x₂ and check (in "parallel") whether x₁ is accepted by M₁ and x₂ is accepted by M₂.

2. L^* is RE. The proof is similar to part 1. The only difference is that the input string has to be divided (nondeterministically) into some substrings x₁, x₂, ..., x_n, where n (also choosen nondeterministically) is not greater than the length of x.

Exercise 3

1. L₁L₂ is Rec. The difference with Exercise 2(1) is that we need to construct a deterministic machine M (because we need to compute a function -- the characteristic function of L₁L₂). This can be done by simulating (via backtracking) the computations of M₁ and M₂ (computing the characteristic functions of L₁ and L₂ respectively) on all the possible divisions of the input string x into substrings x₁ and x₂. If we find at least one division on which both M₁ and M₂ answer "yes", then M answers "yes". Otherwise M answers "no".

2. L^* is Rec. The proof is like Exercise 3(1). The only difference is that the input string has to be divided into some substrings x₁, x₂, ..., x_n, where n is not greater than the length of x. If, for at least one of these divisions, we get that each x_i is in L (i.e. the machine which decides L gives answer "yes" on each x_i) then then answer is "yes". Otherwise the answer is "no".

Exercise 4

1. L₁ is not RE. In fact, the property

   p(L) =def= L is empty

   is not upward closed. Hence if L₁ were RE it would contadict Point 1 of the Lemma of Effective Discontinuity.

2. L₂ is RE, but not recursive. To prove that L₂ is RE, just consider a machine which, given a machine M as input, it generates all possible strings, and tests, for each of them (in "parallel") whether M accetps that string.

   Alternatively, one could use the theorem of Rice-Shapiro. In fact, the set of non-empty languages can be written as the union of all the upward closure of the sets {x}, for any string x. These sets are finite, and they are indexed on the strings on {0,1}, which constitite a RE (even Rec) set.

   To prove that L₂ is not Rec, consider the property

   p(L) =def= L is not empty.

   This property is not-trivial, hence, by the theorem of Rice, L₁ cannot be upward closed.

   Another proof that L₂ is not Rec is the following. Note that L₁ is the complement of L₂ union the set NE = {x in {0,1}^* | x is not the encoding of any TM}. Since NE is Rec, if L₂ were Rec then L₁ would be Rec as well. But we have proved that L₁ is not even RE.

3. L₃ is not RE. In fact, the property

   p(L) =def= L = {0,1}^*

   is not finitely reachable. Hence if L₃ were RE it would contradict Point 2 of te Lemma of Effective Discontinuity.