Data Structures/Automata/Graph Theory Question:

Here are some notes that might help via Google Drive: https://goo.gl/VFeiHV https://goo.gl/629bQb https://goo.gl/rvH97C

a. (5 points) Let To be the Turing machine (whose transition diagram is) shown in Figure 1. Show that go0010 H*101q20 by inserting the intermediate configurations in the sequence 0,001? . . . 101g20. Does 0010 L(T)? 41 0+1, R 1-R 42 accept Figure 1: The Turing machine To. b. Answer TRUE/FALSE and justify your answers. 1. (4 points) A friend of mine claims that they have seen a proof that the language recognized by the Turing machine To (Figure 1) is NP complete. Assuming that NP?P, is it possible that the proof is correct? 2. (2 points) ATM E NP! 3. (4 points) A given undecidable language Ly has a verifier. Is the complement language L mapping reducible to Eara? a. (5 points) Let To be the Turing machine (whose transition diagram is) shown in Figure 1. Show that go0010 H*101q20 by inserting the intermediate configurations in the sequence 0,001? . . . 101g20. Does 0010 L(T)? 41 0+1, R 1-R 42 accept Figure 1: The Turing machine To. b. Answer TRUE/FALSE and justify your answers. 1. (4 points) A friend of mine claims that they have seen a proof that the language recognized by the Turing machine To (Figure 1) is NP complete. Assuming that NP?P, is it possible that the proof is correct? 2. (2 points) ATM E NP! 3. (4 points) A given undecidable language Ly has a verifier. Is the complement language L mapping reducible to Eara