When asked for a machine, please provide a summary high-level description as well as a state diagram 1. (20 points) Consider the language LODD wE 0,1, k >0, and w represents an odd integer in binary ) (a) (10 points) Create a single tape, deterministic Turing machine that recognizes, but does not decide, LoDD (b) (10 points) Create a single tape, deterministic Turing machine that decides LoDD 2. (20 points) ivn your machine in (2b), provide the configuration traces for input strings: (a) (5 points) w = hello (b) (5 points)10o11 (c) (5 points1000 (d) (5 points)0001 3 20 points Consider the language of infinite binary strings B tu w E 0 1 Use Cantor's diagonalization method to prove that B is uncountable. 4. (20 points) SIPSER Exercise 4.1 a, b, c, e, f 5. (20 points) Prove that if A Sm B and B is decidable, then A is decidable NOTE: For 5 you should consider the following definition: Language A is mappnng reducible to language B written A B if there exists a computable function f : ?* ? ?., where for every u, it is the case that w E a?f(w) E B. The function f is called the reduction from A to B