"Guessing" is directly related to our existential interpretation of non-determinism
In a nutshell:
This idea that a non-deterministic automaton can
guess (or be helped by an oracle) is directly related to our existential
interpretation of non-determinism. Another interpretation is
possible (maybe others) where "guessing" would not make sense.
Non determinism is strange. We do have one way of interpreting it in
automata theory, but it is not a priori obvious how we should do that.
It may seem surprising, but non-determinism is a very common
situation. When one has to prove a theorem, given the axioms of some
mathematical theory, the process is naturally a non deterministic one.
That is why we often do not know what to do to solve a problem, for
example to find the solutions of a third degree equation, or prove
There are many ways to combine what is already known with inference
rules to get new results. And the situation is usually the same if we
try to reconstruct a proof backward from the result.
When attempting to solve such a problem, we try to "guess" a path in
some transition system.
Actually, we do not guess, but build in our mind some structure that
organizes and/or simplifies the maze of possibility so that we can see
our path through it. In some cases, the question follows an identified
pattern for which we have a standard way to (sometimes? usually?
always?) find a solution, and we call that an algorithm.
One (usually expensive) technique we can use is simply to fully explore
the maze: to follow all paths, doing it breadth first to avoid being
caught in an infinite subgraph. This is pretty much what is being done
by dovetailing all possible computations of a non-deterministic automaton. This
derived dovetailed computation is itself a deterministic one.
This dovetailed computation $DC$ mimics all possible computations of
the original automaton $A$, but does not tell us how it should be
interpreted. It can just tell us whether A might sometime halt, with
acceptance or rejection, and possibly that it will always halt. But it
cannot, any more than $A$ itself, tell us that $A$ never halts, or never
halt with acceptance.
Actually, there could be different ways of interpreting a
non-deterministic computation. Afaik they are all consistent, but
not with each other.
In the case of a language recognizer $R$, such as a NPDA, that can
either not halt, or halt with acceptance or rejection, the recognizer
is said to accept an input $w$ iff there is one computation that halts
and accept. This is consistent with our own view of the
non-deterministic proof process that is considered successful iff it
can identify one proof tree for the theorem to be proved.
The idea of guessing for the recognizer is just an image taken from
our own way of "guessing" how to find that proof tree. But the big
difference is that our brains are not PDAs. They are much more complex
devices with the ability to explore and map approximately transition
structures so that we can find our way through them, which we
sometimes perceive as guessing.
This interpretation of non-deterministic computation is what I would
call existential acceptance, in reference to the fact that it
requires only the existence of a single accepting computation. It
corresponds to existential halting that I introduced in another
However, one could also interpret non-determinism in a universal way
as: a recognizer is said to (universally) accept an input "w" iff all
possible computations halt and accept the input. This universal
acceptance corresponds to the concept of universal halting introduced
in the same answer.
Universal acceptance, and universal halting seem to lead to a
self-consistent understanding of non-determinism. Hence one could do
theoretical work with that definition. But it is not consistent with
our usual practice in many non-deterministic situations such a theorem
proving, or in everyday life situation. When confronted with a
problem, we only want one way of solving it, and then do not care
whether other ways are successful or not (well this is a bit over
If we have to recognize a palindrome, we can guess by measuring the
length and looking for the middle. The PDA cannot. But, as we are
only interested in existence of one solution, we can always pretend
that it can ... if that will help it. Or we can consider that it has
oracles provided by more intelligent machines (us?) to help it. Or you may even call it magic, and think it is (after all, the existential quantifier is a kind of magic wand). If it
can help, it will. If there is no accepting computation, no help
whatsoever will be any use.
Note that this idea of guessing would be meaningless in the universal