Nondeterministic Turing machines, tape "forking" and shared memory

83 Views Asked by At

I'm describing a nondeterministic Turing machine solving a problem in $NL$-space. Of course I'm making good use of the fact that along with each computational branch, my tape is also "forked".

My question is whether it's legal to update a "shared" memory slot -- that is, a memory slot initialized before the nondeterministic branching, and then not "forked"? We're describing Turing machines in free-form at this point rather than with formal definitions, but I don't want to frivolously do something that the model wouldn't allow.

On a regular computer, that'd be like a forked process updating a shared memory segment, but I understand this is a weak analogy for something as theoretical as a Turing machine :)

1

There are 1 best solutions below

0
On BEST ANSWER

No -- letting the different worlds communicate with each other would lead to a model of massive parallellism rather than one of non-determinism.