Do NFAs with $\varepsilon$-moves never terminate? Suppose in an NFA we have an $\varepsilon$-move from a state $q_0$ to $q_1$. According to Sipser,


  Without reading any input, the machine splits into multiple copies one following each of the exiting $\varepsilon$-arrows and one staying at the current state. Then the machine proceeds nondeterministically as before.


Here is an application of this logic to our case: upon reaching the state $q_0$ our machine splits into two copies: one in state $q_1$, one in state $q_0$. For the latter copy, execution continues as before, so again another copy of the machine is created in state $q_0$. Thus, a copy of the machine always in state $q_0$ will exist indefinitely.

Is this true? If no, why not? How should I then interpret the description given above?
Sipser proposes an operational intuition for non-determinstic machines. As you have experienced, it's not very useful. In particular, it doesn't relate a lot to the formal definition, and there are more problems down the road¹.

I recommend sticking to the definition: an NFA accepts an input if there is a path from a starting to a final state labelled with the input. That really tells you all you need to know, and all there is to know.

Try to think mathematically instead of computationally.




Parallelism and non-determinism are not the same; you can not build non-deterministic machines in a meaningful sense; cost models (e.g. in complexity theory) for non-deterministic machines don't make sense if you have the split/fork intuition; ...