In lecture this week, we have finally reached the Turing machine model and with it we have reached a mathematical model that can represent all possible computation. Along with this brings a leap in abstraction since the content will now shift to problems at a more philosophical level: what can and cannot be computed? To get there, we need a thorough understanding of the inner workings of the Turing machines, including how computation is performed. To demonstrate types of problems that cannot be computed, we will/have introduced a number of decision problems that ask questions about the behavior of a particular piece of “source code”.
Problem 1. Complete the TopHat worksheet
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.
