1. Update the given graph as little as possible to obtain the graph of a Turing machine multiplication which takes two numbers n and m written as sequences of 1 s and returns the number n followed by the number m followed by their product. The numbers n,m and their product should be separated by the symbols of choice (avoid the blank symbol). [1] For example, if you choose and then input and output tapes may look as follows: 2. Recall that the difference between your proposed graph and the given graph should be minimal. Clearly highlight this difference. 3. Give the formal definition of your proposed graph including the start state and action table. 4. Implement your graph in the language of your choice. Explain why you chose that language. 5. Give the logic of your graph (i.e., clearly explain how it works and say what each part of the graph actually does). 6. Associate each part of your graph to the relevant part of your code (i.e., explain how each part of your graph is implemented in your chosen language). 7. Test your program to multiply each of the following pairs of numbers: 0 and 3. 5 and 0. 3 and 2. 1 and 5. Where for each of the above test cases, you print all the tape computation sequences from start to end together with the states, the location, the content of the tape, etc., and you include the count of the number of tapes produced. [4] 8. Comment on the efficiency of your program from the point of view of the number of tape computation sequences produced, and the time taken to finish each test. 9. Update your multiplication machine graph to produce the graph of a power of 3 Turing machine (i.e., the Turing machine that takes a number n and returns n3 which is n to the power 3). 1. Update the given graph as little as possible to obtain the graph of a Turing machine multiplication which takes two numbers n and m written as sequences of 1 s and returns the number n followed by the number m followed by their product. The numbers n,m and their product should be separated by the symbols of choice (avoid the blank symbol). [1] For example, if you choose and then input and output tapes may look as follows: 2. Recall that the difference between your proposed graph and the given graph should be minimal. Clearly highlight this difference. 3. Give the formal definition of your proposed graph including the start state and action table. 4. Implement your graph in the language of your choice. Explain why you chose that language. 5. Give the logic of your graph (i.e., clearly explain how it works and say what each part of the graph actually does). 6. Associate each part of your graph to the relevant part of your code (i.e., explain how each part of your graph is implemented in your chosen language). 7. Test your program to multiply each of the following pairs of numbers: 0 and 3. 5 and 0. 3 and 2. 1 and 5. Where for each of the above test cases, you print all the tape computation sequences from start to end together with the states, the location, the content of the tape, etc., and you include the count of the number of tapes produced. [4] 8. Comment on the efficiency of your program from the point of view of the number of tape computation sequences produced, and the time taken to finish each test. 9. Update your multiplication machine graph to produce the graph of a power of 3 Turing machine (i.e., the Turing machine that takes a number n and returns n3 which is n to the power 3)