0
$\begingroup$

Does an NDTM have the power to combine computational branches ie. can a result from branch A be used in the next step in the computation along branch B? Can branches use each others' results, diagrammatically 'merging'?

Example:

Branch i arrives at the number b after n steps, branch j arrives at the number c after 2n steps. After we have waited for both to arrive at their respective values, the computer, on the next step, multiplies those values 3*5 (effectively merging the different branches). Can it do this?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

One view, explained by Tom here, is that nondeterministic branches work in parallel.

A more standard view, I think, is to view nondeterminism the way it is treated in physics, in logic, and in Dijkstra/Hoare style algorithm specification: at certain points, multiple continuations are possible, one of which will be taken. The 'multiple possible universes' do not exist in parallel, but they are alternative potential states of the world, alternative ways for the algorithm to continue, one of which will become reality.

So no, steps taken in one branch are not available in another branch. You either follow one branch or the other.

Improve this answer
$\endgroup$
3
$\begingroup$

No, that's not how non-determinism work.

You can think about non-determinism as parallel universes. All the branches runs concurrently, in a different plane, and to itself it seems like it's the only run in the world.

The language accepted by a non-deterministic turing machine is every word that there exists a universe (or respectively a run) such that it gets accepted in it. So in that sense, non-determinism means run all the possibilities, and choose the best one.

Improve this answer
$\endgroup$
2
  • $\begingroup$ makes sense, but i cant accept because don't know if correct. Is there another commonly studied / known / named model of comp that lets the branches interact? $\endgroup$
    – DeeDee
    Commented Jun 11, 2020 at 2:35
  • 1
    $\begingroup$ @DeeDee A parallel machine with exponentially many processors and polynomial time and space per processor effectively gives you "communicating branches". To my knowledge, there isn't a standard name for such a machine that is shorter than what I just wrote. $\endgroup$
    – Aaron Rotenberg
    Commented Jun 11, 2020 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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