Defining the halting problem for non-deterministic automata

The primary definition of Turing machine (TM), at least in my own reference
textbook (Hopcroft+Ullman 1979) is deterministic.

Hence my own understanding of the halting problem is primarily for
deterministic TM, though I am aware that it may be considered for other kinds of automata.

I also noticed that determinism is often more or less implicit in the way
people often refer to TM or to the halting problem. The wikipedia page
on the halting problem is a good example of that.

But, there seem no reason for such a limitation. Given a family
$\mathcal F$ of automata that can be non-deterministic, the halting
problem for $\mathcal F$ may be defined as:


Is there a uniform decision procedure such that, given an automaton $A\in\mathcal F$ and an input $x$, it can decide whether there is a
halting computation of $A$ on input $x$.

(This is not quite the same as saying that the computation of $A$ with input $x$ will terminate.)

Indeed, that seem the only way to give some sense to discussions about
the halting problem for Linear Bounded Automata (LBA) which are
primarily non-deterministic automata.

So my question is whether I am correct, and whether there is a reason (and which reason)
for this apparently second class treatment of the halting problem for
non-deterministic automata.

There are a few reasons I think we put less effort into the Halting problem for non-deterministic models.

The first is that there are, in fact, two relevant halting problems for a ND model. Given an input $x$ and a non-deterministic machine $M$:

• Does there exist a valid run of $M$ on $x$ which halts?

• Does there exist a valid run of $M$ on $x$ which doesn't halt? i.e. do all valid runs halt?

For deterministic machines, these are identical, since there is exactly one valid run of $M$ on an input $x$. But for non-deterministic machines, there might be multiple runs. Which one you're interested in depends on your application.

Secondly, non-deterministic models are already unrealistic: they assume that you either have a magical box telling you which path to take, or that you have some form of infinite parallelism. Since non-deterministic and deterministic Turing Machines are equivalent in power, in most cases you just convert the machine into a determinstic one before you worry about halting.

As an extension of this, we don't care because proving something about a non-deterministic machine is at least as hard as proving something about an equivalent deterministic machine. We already know that there's no solution to the deterministic Halting Problem, so all it's really useful for is proving other problems undecidable through reductions. And it's always going to be less work to reduce to the deterministic halting problem, since it's easier than it's non-deterministic counterpart.

StackExchange Computer Science Q#44231, answer score: 12