In a nutshell
There seems to be no good reason to neglect the halting problem in
settings that are not the classical one of deterministic Turing
machines, other than the fact that the classical halting problem
answers some major mathematical questions (such as the
Entscheidungsproblem), while variants are only interesting (?) technical
issues, but with less impact on the foundations.
After reviewing some of the arguments given in previous answers, I analyze and
compare the two proposals by jmite for a possible definition of
"nondeterministic" halting in the case of nondeterministic
automata. The issue is not to define what halting means for a single
computation, but what it should mean for the set of possible
computations of a given nondeterministic automaton $A$ on a given
input $x$. This can then serve as a basis for defining the halting
problem on nondeterministic automata.
According to jmite's answer, this nondeterministic halting can be
defined as corresponding to the existence of at least one halting
computation (existential halting), or alternatively to requiring
that all possible computation be halting (universal halting). These
two definitions correspond to two different definitions of the
nondeterministic halting problem.
I show that, for Turing machines, the two definitions corresponds to
two distinct ways of determinizing the machine by dovetailing. From
this, I infer that the two variants of the nondeterministic halting
problem are both Turing equivalent to the classical deterministic
However, I also show that each of these definitions of halting is directly
related to a corresponding definition of the language recognized by a
Turing machine, and this relation can be simply expressed on the
condition of choosing consistent definitions.
Hence, given the usual definition of the language recognized by a
nondeterministic automaton, the natural definition of nondeterministic
halting is existential halting, as proposed in the original question.
Most of this analysis naturally extends to other types of automata,
though the dovetailing constructions are often not available within
less powerful families than Turing machines.
I am writing this as an answer since it partially answers my question
after more thoughts about it, taking existing answers into account. Also, editing my question after three
answers might in this case confuse issues, and I would rather leave
the question as originally written to avoid that.
I first discuss some of my disagreements with the given answers. The
point is not to disparage fair attempts at answering my question (my
thanks for all answers), but to get to the bottom of issues by
discussing or disputing technical points.
I think the original question hardly needs context or motivation. The halting
problem is one of the major questions we ask about automata on the one
hand, and nondeterminism is one very common and useful features of
many automata on the other hand. Furthermore, nondeterminism is not
just a common theoretical device to simplify proofs, but an essential
feature of some families of automata, such as the linear bounded
automaton (LBA), at least at the time of this writing.
Hence it is quite natural to wonder whether the halting problem has
meaning, or a preferred meaning, which and why, in the case of
Is the nonderterministic halting problem well addressed?
My question wonders why the halting problem for nondeterministic automata
seems to receive second class treatment, which did generate a downvote
and an answer by vzn. The answer by vzn, which is really more a long
comment, insists that "nondeterminism seems a very deep/ ubiquitous/
crosscutting concept in CS", which I never doubted. It also gives one
reference to some reasearch on halting for nondeterministic machines
which is not surprising, but does not really address my point. My
point is that I do not recall actually seeing a definition of the
halting problem aimed at nondeterministic machines, though I did read
some litterature in the field. It is not addressed, AFAIK, in my
reference textbook (Hopcroft+Ullman 1979). It seem often implicit in
the mind of people that they are considering deterministic automata,
usually Turing machines, whose reference definition is deterministic.
For example, in the question Why is the halting problem decidable for
LBA?, Yuval Filmus forgot in his answer that LBAs are nondeterministic
devices - but brilliantly saved his answer with a 4 words comment.
As a last witness to the fact that this issue is not well addressed in
general (despite some specialized research), I would call the fact
that the issue has to be discussed here.
The answer from jmite is the only one that actually attempts to explain
why it might not be well addressed. His first argument is that there are
two possible definitions, but I believe that this situation should
rather encourage more analysis to determine which definition would be
most appropriate. I attempt to do that below.
He also suggests that, since a nondeterministic TM can always be
converted into an equivalent deterministic one, there is not much
point in worrying about the issue of halting in the nondeterministic
case. I am not fully convinced, but it may be perceived as a good
reason by many. However, the argument does not apply to Linear Bounded
Automata (LBA), because it is still an open problem whether
deterministic LBA are equivalent to nondeterministic LBA. And there
are other families of automata for which the deterministic subfamily
is weaker that the whole nondeterministic family (PDA for example).
I also disagree with the last point, asserting that we should not be
concerned with nondeterministic halting because proofs are easier
with deterministic machines. Raphael objected to that in a comment:
"I usually find reductions to harder problems easier". Indeed, for
many types of automata, the nondeterministic version serves mainly to
simplify proofs, such as reduction to that type of automaton. Having
in addition two forms of halting that may be used, as suggested by
jmite himself, could even be considered an advantage as it give more
flexibility to address problems.
On the definition of the nondeterministic halting problem
Note: the use of the word "universal" in the following text refers
to universal quantification, NOT to universal Turing machines
The answer from jmite is the most detailed.
This answer conjectures that nondeterministic automata foster less
effort on the halting problem because it can be defined in two
different ways (the terminology is mine):
The only definition I had suggested adequate is existential halting.
Proposition 1: When a nondeterministic automaton is universally
halting on input $x$, it can only have a finite number of halting
computations on that input.
Proof: This is easily proved with König's lemma, since the
number of possible nondeterministic choices at each step is bounded
for a given automaton. If there were infinitely many halting
computations, we could label each configuration with each of the
computational paths leading to it, which would make a computation
graph with infinitely many nodes, but only finite nondeterministic
branching at each node. By König's lemma, this implies the existence
of an infinite computational path, corresponding to a non-halting
The case of (nondeterministic) Turing machines
So now, let's examine halting in the case of nondeterministic Turing
To analyze the two definitions, the simplest is indeed to consider
deterministic versions of non deterministic machines, which can be
achieved, as recalled by Hendrik Jan, by dovetailing of all possible
But there are (at least) two ways of dovetailing computations for
determinization, though only one is usually considered:
existential dovetailing determinization which simulates all
computations in parallel and terminates when one of the simulated
universal dovetailing determinization which simulates all
computations in parallel and terminates only when all of the
simulated computations terminate. But it can conceivably
enumerates in some way the terminating computations, or count them.
A nondeterministic TM $M$ is existentially halting on input $x$ iff
its existential dovetailing determinization $M_\exists$ is a TM that
halts on input $x$.
A nondeterministic TM $M$ is universally halting on input $x$ iff
its universal dovetailing determinization $M_\forall$ is a TM that
halts on input $x$.
Proof: The proof for the existential case is obvious. For the
universal case, the universal dovetailing determinization will halt
iff it simulates a finite number of computations, all of which are
halting. Given a nondeterministic TM $M$, if it halts universally on
input $x$, then, by proposition 1, it has only a finite number of distinct
computations, which all halt. Hence its universal dovetailing
determinization $M_\forall$ halts on input $x$. The converse is
Theorem 3: The halting problem for deterministic TM, and the existential
and universal halting problems for nondeterministic TM are Turing
Proof: This results from proposition 2 and from the fact that
deterministic TMs are a subset of nondeterministic TM, where both
existential and universal halting reduce to simple deterministic
Hence, from a computability point of view, and I am tempted to say
from a symbol pushing point of view, it seems that it does not
really matter which definition is chosen, existential or universal,
for the nondeterministic halting problem.
Why choose one definition of NTM halting, and which
However, is there much sense to a determinization process that does
not preserve the language recognized by the original automaton?
The essence of the use of nondeterminism in language recognition is
that it assumes an oracle that is supposed to guess a right
computational path whenever there is one that will lead to acceptance,
a fundamentally existential view.
In a nondeterministic computation, there is no difference between
rejection on halting and non-halting. In both cases, no conclusion can
be drawn. The language recognized is not changed if you replace
rejection on halting by a non-halting infinite loop, which can be done
for all nondeterministic automata I can think of, including NFA (just
add a looping $\epsilon$-transition on the failure states). This is
also true of deterministic automata, provided there is a special
symbol marking the end of the input, as usually done for LBA.
Thus acceptance by halting may be seen as a canonical form of
acceptance for nondeterministic automata.
Considering this canonical view, the halting problem may also be expressed
equivalently as the recognition problem:
Is there a uniform procedure that, given a language $L$ recognized
by a Turing machine $M$, can decide for any word $x$ whether $x\in L$?
This evidences the close ties between recursive enumerabiliy and the
halting problem. This equivalence between deciding halting of the TM $M$
on input $x$ and containement of $x$ in the language $M$ recognizes is
true for both deterministic TM and for nondeterministic ones,
provided we consider the existential definition of nondeterministic
However, in the case universal halting, this close relation is lost. A
similar statement can be made, but for a different language than the
one recognized by the NTM (or alternatively for a different,
universal, definition of what is the language recognized by a NTM).
When developing a theory, it is essential to use consistent
definitions so as to emphasize structures and relations in their
simplest and most perspicuous form. It is quite clear that in the
present case, consistency with other definitions suggests that
existential halting is the natural definition of halting for
nondeterministic Turing machines.
Of course, one may always be interested in analyzing universal
halting. Similarly, one could also develop a theory of universal
acceptance for NTM based on the requirement that a string $x$ is
accepted iff all computation on input $x$ halt and accept. But,
apparently, it is not considered a major issue in the theory of Turing
The case of other families of automata
Parts of the above analysis cannot be extended to most families of
nondeterministic automata. For example a pushdown atomaton (PDA) may
define languages that cannot be recognized by a deterministic PDA.
The same may be true of LBAs. Other parts can be extended to all
Regarding the definition of nondeterministic halting, even though the
reasoning used in the Turing machine case may not be usable, it seems
that the only sensible choice is to adopt a definition which is
consistent with the one used for nondeterministic Turing machines,
hence the existential definition.
The definition of the Halting problem for these families of
nondeterministic automata follows, and conforms the definition
proposed in the question.