Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.