a. Suppose you had a NON-Deterministic Turing Machine that atsome point was in the start state q0 over a tape that is completelyblank except for one cell which contains a # symbol. If theread/write head is currently over a blank cell and you do not knowwhere the # lies with respect to the current position then whatwould you need to do to move the read/write head so that it is overthe # and in state p how would you accomplish this? Build theNON-Deterministic machine that will halt with the R/W headpositioned over the # symbol.
b. Solve the previous problem by building a purely DeterministicTuring machine. Explain how the machine works and how it differsfrom the non-deterministic version. This machine MUST beDeterministic.