Simulating Non Deterministic Turing machine with Deterministic Turing machine [JFLAP]

Question

Problem: Given a start state q0, and a completely blank tape except for one square with a # symbol, find the # and halt on it.

Non-Deterministically:

This machine chooses to either search left or right of the start state, and keeps going in that direction until the next symbol is the # symbol, where it stays.

Deterministically: ?

How do I replicate this machine in a deterministic form? I've done some research and it seems this problem can be solved by addressing both possibilities/branches of the "tree", but I can't seem to connect the dots here...

Answer 1

You do not just run over the non-# cells, but you mark them as visited. Further you do the two branches simultaniously by alternating between them.

1. Mark the current cell with "+" (unless it is the # already)
2. Run to the right while you see +. When you see the first blank, mark it +.
3. Run to the left while you see +. When you see the first blank, mark it +. Go to 2.

In this way you can process any fixed number of non-deterministic branches in a deterministic way. Of course, the running around takes much more time than the actual simulation.