Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :)

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.