Define a Turing machine that, for any word w over the alphabet {0, 1},
outputs ww (that is, the machine starts with w and halts with a tape
containing ww).
Show that if a language L over the alphabet X can be recognised by a
Turing machine, then the following languages are also recognisable:
a) the complement of L (that is, the set of all the strings over X that are
not in L);
b) the union of L and another decidable language L
′
;
c) the concatenation of L and another decidable language L
′
(that is, the
language consisting of all the words that can be formed by concatenating a word from L and a word from L
′
);
d) the intersection of L and another decidable language L
′
.