a. Suppose you had a NON-Deterministic Turing Machine that at some point was in the start state q0 over a tape that is completely blank except for one cell which contains a # symbol. If the read/write head is currently over a blank cell and you do not know where the # lies with respect to the current position then what would you need to do to move the read/write head so that it is over the # and in state p how would you accomplish this? Build the NON-Deterministic machine that will halt with the R/W head positioned over the # symbol.

b. Solve the previous problem by building a purely Deterministic Turing machine. Explain how the machine works and how it differs from the non-deterministic version. This machine MUST be Deterministic.