Turing machines and Computability, I

Construct explicit Turing machines for the following functions:

1. Neg : {0, 1}^{∗} → {0, 1}^{∗} , where Neg(x) is obtained from x by replacing the symbols 0 by 1 and 1 by 0.

2. Even : {0, 1}^{∗} → {0, 1}, accepting a word x iff x has an even number of symbols.

3. (Unary addition) Add : {0, 1}^{∗} → {1}^{∗} mapping

\underbrace{1 … 1}_{n times} 0 \underbrace{1 … 1}_{m times} ⟼ \underbrace{1 … 1}_{n+m times} .

4. (Huiswerk) Inv : {0, 1}^{∗} → {0, 1}^{∗} rewriting a word x in reverse order. Describe on the level of implementation:

5. Simulate any TM by a TM with the tape alphabet {0, 1, ⊔}.

6. Invent a definition of a 2-dimensional Turing machine and show its

equivalence with a standard TM. For the rest of your life you may use Church-Turing Thesis.

7. Show that the class of Turing recognizable (r.e.) languages is closed under union, intersection, concatenation.

8. Prove: an infinite subset of N is decidable iff there is a TM enumerating it in strictly increasing order.

9. Show: there is a language which is not r.e. Give an example.

10. Is there a language L such that neither L nor the complement of L is r.e.? (^{∗}) Give an example.^{1}

11. There is a partial computable function f : N → N which has no total computable extension. (Try to play with the universal function.)

1(^{∗}) means ‘a more difficult problem’.