nondeterminism is not randomness

It is tempting to picture a nondeterministic machine as one that flips a coin at each fork and hopes for the best. That picture is wrong, and the difference matters. Nondeterminism has no coins, no probabilities, and no luck. There is no chance that the machine "chooses badly" and rejects a string it should accept. The definition is purely about EXISTENCE: a string is accepted if at least one accepting path exists, full stop.

Contrast the two ideas precisely. A randomized machine has probabilities on its choices and might accept the same input with probability, say, 0.9 — you can run it and sometimes get the wrong answer. A nondeterministic machine has no probabilities at all; "acceptance" is a logical claim about the tree of all possible runs (does an accepting leaf exist?), not the outcome of any single physical run. Nondeterminism is therefore a definitional and descriptive device — a way of specifying a language — not a description of how any real machine operates moment to moment.

Two practical consequences follow. First, real hardware does not get nondeterminism for free; to actually decide acceptance, a deterministic computer must search or simulate the whole tree of choices (for an NFA, by tracking the set of possible states). Second, when this idea returns as the class NP, the stakes rise: NP is defined by nondeterministic polynomial time, and whether that existential guessing can always be simulated deterministically in polynomial time is the open P-versus-NP problem. Keeping "nondeterministic" cleanly separate from "random" is essential to understanding both finite automata and complexity theory.