Description
Problem 1. (42 points) Complete the TopHat worksheet titled Spring 2020 HW5.1. There are a total of 21 questions, each worth 2 points.
Problem 2. (18 points) 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.
