Can an $NDTM$ simultaneously perform a set of operations on all strings of a given length?
The easier way to think of NTM's is not as they are capable of &quot;spawning branches&quot;, but as they are capable of &quot;splitting into two branches, and each branch knows who it is (the first branch is 0, and the second is 1)&quot;
In this way of thinking (that also actually represents what's going on inside the TM), splitting into $2^b$ branches means doing the &quot;split&quot; 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 &quot;0&quot; branch splits into branches &quot;00&quot; and &quot;01&quot; (notice that these are not numbers! They are strings) and the &quot;1&quot; branch splits into &quot;10&quot; and &quot;11&quot;.
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)