Can a non-deterministic machine merge its branches?

Question

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?

Answer 1

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.

Answer 2

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.