Assignment 8

In the following questions, “show” means to describe, to at a fairly high level (no need to go down to the transition-function and state level), the Turing machine that carries out the required task.

1. Suppose that \(A\) and \(B\) are two decidable languages.
   1. Show that the complement of \(A\) is decidable.
   2. Show that their union is decidable.
   3. Show that their intersection is decidable.
   4. Show that their concatenation is decidable.
   5. Show that the Kleene star \(A^*\) is decidable.
2. Suppose that \(A\) and \(B\) are Turing-recognizable languages.
   1. Show that their union is Turing-recognizable.
   2. Show that their intersection is Turing-recognizable.
   3. Show that their concatenation is Turing-recognizable.
   4. Show that the Kleene star \(A^*\) is Turing-recognizable.
3. Suppose \(A\) and \(B\) are two languages, and \(B\subset A\). Assume further that \(A\) is decidable. Recall that we denote by \(A^c\) the complement of \(A\).
   1. Show that \(B^c\) is Turing-recognizable if and only if \(A\cap B^c\) is Turing-recognizable. (Hint for one direction: \(B^c = A^c \cup (A\cap B^c)\)).
   2. Show that \(B^c\) is decidable if and only if \(A\cap B^c\) is decidable.
4. Consider a Turing Machine with at least 4 tapes, and on the first two tapes we have two binary numbers stored, with their least significant digit at the left-most position. So for example \(6\) would be stored as \(011\). Describe in some detail the following two parts of a Turing Machine:
   1. A part that writes in the third tape the result of adding the two numbers together.
   2. A part that writes in the fourth tape the result of multiplying the two numbers together. You can use the previous part along the way, and you can also use more tapes if you need them.