Problem 1. Complete the TopHat worksheet titled Spring 2020 HW5.1. There are a total of 21 questions, each worth 2 points.
Problem 2. Prove that the following language L is Turing decidable by constructing a 3-tape (or fewer) Turing machine that recognizes and decides it.
L = {x#y#z | x,y,z ∈ {0,1}∗,x + y = z (as binary numbers)}.
Your answer will not be accepted without the following:
2(a) A high-level pseudocode for your solution.
2(b) For each step of your pseudocode, a Turing-machine level explanation of how you can approach that. 2(c) The Turing machine diagram for each step of the pseudocode.
You may use the JFlap program to aid with your design. The overall diagram is not really important as long as you have provided the step-by-step instructions and explanation. For more on this, review the lecture on 2020-03-24 where we had a high level pseudocode where we broke out the steps into Turing machine concepts and drew a localized Turing machine diagram. If you do build your diagram in JFlap, please include a screenshot in your submission PDF.
