<p>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.</p>

<p>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.</p>

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

<p>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, <a href="https://cs.stackexchange.com/questions/44231/defining-the-halting-problem-for-non-deterministic-automata">Defining the halting problem for non-deterministic automata</a>, but
was a bit disappointed by answers, and ended up answering it myself (how well, I do not know).</p>

<p>Other issues I have in mind are:</p>

<ul>
<li><p>what would be a proper definition of a family of automata defining
a model of computation? Should it satisfy some closure property or other?</p>

<p>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.</p></li>
<li><p>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?</p>

<p>I am not even sure whether stating that there is a standard
encoding has any meaning.</p></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2015-07-30T15:40:55.040Z
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.
vzn
CC BY-SA 3.0
2015-07-31T11:30:31.810Z
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$.
Martin Berger
CC BY-SA 3.0
2015-07-31T12:04:48.540Z
@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](http://www.sciencedirect.com/science/article/pii/0020025573900364),
unless there are new results I do not know.
babou
CC BY-SA 3.0
2015-07-31T12:34:26.393Z
There are no known natural models between the Turing RE degree and Recursive degree.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-07-31T12:53:36.807Z
@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](http://cs.stackexchange.com/questions/44763#44766), not
contradicted by the author of the answer).
babou
CC BY-SA 3.0
2015-07-31T16:05:30.313Z
agreed with MAT that your question seems to ask for a language class "between" or "intermediate" within Recursive/ RE and apparently none are known or maybe arent even possible. see also [Chomsky hierarchy](https://en.wikipedia.org/wiki/Chomsky_hierarchy). but maybe there is some rough concept of "hardness" of [termination analysis](https://en.wikipedia.org/wiki/Termination_analysis) of different programs?
vzn
CC BY-SA 3.0
2015-07-31T19:13:41.863Z
@MohammadAl-Turkistany Would you consider LBA as a model of computation?  I think that LBA halting is not LBA-decidable, and that Iit can be proved with the usual diagonalization argument. Or am I mistaken?
babou
CC BY-SA 3.0
2015-08-01T00:12:00.340Z
@babou The Halting problem for LBA is decidable so it is in the REC degree. See this post: http://cs.stackexchange.com/questions/22925/why-is-the-halting-problem-decidable-for-lba
Mohammad Al-Turkistany
<computability><halting-problem>
The halting problem in computational models weaker than Turing machines
babou
# The halting problem in computational models weaker than Turing machines

(Asked by: username_0 on 2015-07-30)

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](https://cs.stackexchange.com/questions/44231/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.

**Tags:** computability, halting-problem

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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$.  
> **username_0**: @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](http://www.sciencedirect.com/science/article/pii/0020025573900364), unless there are new results I do not know.  
> **username_3**: There are no known natural models between the Turing RE degree and Recursive degree.  
> **username_0**: @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](http://cs.stackexchange.com/questions/44763#44766), not contradicted by the author of the answer).  
> **username_1**: agreed with MAT that your question seems to ask for a language class "between" or "intermediate" within Recursive/ RE and apparently none are known or maybe arent even possible. see also [Chomsky hierarchy](https://en.wikipedia.org/wiki/Chomsky_hierarchy). but maybe there is some rough concept of "hardness" of [termination analysis](https://en.wikipedia.org/wiki/Termination_analysis) of different programs?  
> **username_0**: @MohammadAl-Turkistany Would you consider LBA as a model of computation?  I think that LBA halting is not LBA-decidable, and that Iit can be proved with the usual diagonalization argument. Or am I mistaken?  
> **username_3**: @username_0 The Halting problem for LBA is decidable so it is in the REC degree. See this post: http://cs.stackexchange.com/questions/22925/why-is-the-halting-problem-decidable-for-lba  

---

## 0 answers

