[4 points] Describe a Turing Machine that accepts { 0n | n is a power of 2 }. We want a high-level description of this machine in 10 or fewer clear English sentences. Do not give a list of transitions.
[4 points] Describe a Turing Machine that, on input an, halts with am on the tape where m = n2. We want a high-level description of this machine in 10 or fewer clear English sentences. Do not give a list of transitions.
[6 points] Show that the recursively enumerable languages are closed under
union and
intersection.
[4 points] Show that { anbnanbnanbnanbn | n ≥ 1 } can be written as the intersection of two context free languages.