Can an $NDTM$ simultaneously perform a set of operations on all strings of a given length?

Question

Can an $NDTM$ perform a set of operations on all strings of a given length $b$, at the same time? Aka can it operate on all strings of a given length by doing something like: spawn $2^b$ branches then operate on each string of length b on each branch?

How could it do this tho if the branches can't communicate? That's what I'm having a hard time with. How does any given branch, if it doesn't know what strings the other branches are running, know what string to run the operations on (so that all the strings are covered by $2^b$ branches)?

Answer 1

The easier way to think of NTM's is not as they are capable of "spawning branches", but as they are capable of "splitting into two branches, and each branch knows who it is (the first branch is 0, and the second is 1)"

In this way of thinking (that also actually represents what's going on inside the TM), splitting into $2^b$ branches means doing the "split" operation $b$ times.

Lets do a simple example with $b=2$:

In the first split, we have two branches: 0,1. In the second split, the "0" branch splits into branches "00" and "01" (notice that these are not numbers! They are strings) and the "1" branch splits into "10" and "11".

Notice that every string of length 2 is either one of the 4 final branches, and therefore this is how we would be able to non-deterministically check every string of length $b=2$.

The same applies for any other $b$ (note that if its not a constant, it will maybe harm the time or space complexity of the machine)