Suppose Non Deterministic Turing Machine Point Start State Q0 Tape Completely Blank Excep Q25346854

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.

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published. Required fields are marked *