State and prove an s-m-n theorem for programs. 2. Describe how the universal Turing machine locates a particular instruction on its description tape. 3. Show that the class of sets accepted by Turing machines is closed under union. (HINT: do not copy the intersection proof.) 4. We know that we can transform Turing machines into programs. In particular, we can find a program equivalent to the universal Turing machine. Design (in the NICE language) a program named Pu such that: Pu(i, x) = Mi(x) for every Turing machine Mi and input x. 5. Show that with the program Mu from the last problem and the s-m-n program, we can design a function trans(n) which transforms Turing machines into programs. That is, if trans(i) = k then for all x, Mi(x)= Pk(x) where Mi is a Turing machine and Pk is a program.