What are the main results and/or literature on the (self) halting problem for other machines than Turing machines? Alternatively, what would be the right keywords or tags to search for it.

I am considering of course the ability to determine halting on given input of automata in a family $F$ by one of the members of $F$, i.e. the $F$-decidability of the halting problem for $F$-automata.

I am not here interested in hypercomputation, but rather in "hypocomputation", i.e. computational models that are weaker than Turing machines.

One problem I looked at is the definition of halting for non-deterministic models of computation, since non-determinism can make a difference for PDA and possibly for LBA. I asked a question on that, Defining the halting problem for non-deterministic automata, but was a bit disappointed by answers, and ended up answering it myself (how well, I do not know).

Other issues I have in mind are:

  • what would be a proper definition of a family of automata defining a model of computation? Should it satisfy some closure property or other?

    The reason is that one can contrive simple collections of automata such that one of them will decide halting for the whole family. But it does not seem very meaningful, if that is all the family has to offer.

  • when asking one automaton $H$ to decide on halting of automaton $A$ on input $I$, is one free to encode $A$ and $I$ in whatever way is deemed convenient?

    I am not even sure whether stating that there is a standard encoding has any meaning.

I realize the question is open. But I do not know how much may exist as possible answer, possibly little. If it is too wide, suggestions to tighten it would be welcome.

  • $\begingroup$ there may be some difficulty here because the halting problem seems to be "either-or" as far as decidability and weaker models for "termination analysis" exist but are decidable. and is that just "too different" than the halting problem? the "weaker version/ analogy" of the halting problem seems to be simply the problem of determining membership of a string in some language from some language class. $\endgroup$
    – vzn
    Commented Jul 30, 2015 at 15:40
  • $\begingroup$ Maybe one closure property for a family $F$ of automata to define a suitable model of computation would be the existence of an $F$-universal $u \in F$, such that for each $f \in F$ and input $i$, $u\; f\; i$ is 'somehow' equal to $f\; i$. $\endgroup$ Commented Jul 31, 2015 at 11:30
  • $\begingroup$ @MartinBerger Relation with the existence of a universal machine does come to mind since we often want to be able to simulate (as in dovetailing). An alternative though is sub-automaton calling in some constructions, not all. But it works for oracle situations, which is the case in the diagonalization construction. This also indicate that universal machines may not exist in situations where the halting problem does have meaning. For example we do not quite have universal LBA, unless there are new results I do not know. $\endgroup$
    – babou
    Commented Jul 31, 2015 at 12:04
  • 1
    $\begingroup$ There are no known natural models between the Turing RE degree and Recursive degree. $\endgroup$ Commented Jul 31, 2015 at 12:34
  • 1
    $\begingroup$ @MohammadAl-Turkistany Sorry for my ignorance. What is covered by recursive degree, and can you be more explicit about what you mean by "no natural models" between Turing RE and Recursive degree. Some people seem to assert that $F$-halting may be $F$-decidable for families $F$ weaker than Turing machines (see the comments of this answer, not contradicted by the author of the answer). $\endgroup$
    – babou
    Commented Jul 31, 2015 at 12:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.