Problems 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 E 10,1, k0, and w represents an odd integer in binary (a) (10 points) Create a single tape, deterministic Turing machine that recognizes, but does not decide, LoD (b) (10 points) Create a single tape, deterministic Turing machine that decides LoDD 2. (20 points) Given your machine in (2b), provide the configuration traces for input strings: (a) (5 points)w-hell b) (5 points)1011 (c) (5 points)1000 (d) (5 points)0001 3. (20 points) Consider the language of infinite binary strings Bw 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, 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 mapping reducible to language B, written A B, if there exists a computable function f : ?. + ?*, where for every w, it is the case that w E a?f(w) E B. The function f is called the reduction from A to B