<p>Considering how parameter passing to subroutines and a huge part of memory management in mainstream computer languages is stack based, an obvious and natural variation is to restrict the unbounded memory of a Turing machine to be a stack.</p>

<p>Such a <a href="https://cs.stackexchange.com/questions/43152/smallest-class-of-automata-model-whose-corresponding-language-class-contains-cfl/43154#43154">model has nice properties</a>, in addition to halting being decidable (well known for <em>PDA</em>s):</p>

<blockquote>
  <p>The notion of a <em>PDA</em> can be generalized to an <em>$S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA)</em>. It consists of</p>
  
  <ol>
  <li>a read-only input tape, surrounded by endmarkers,</li>
  <li>a finite state control,</li>
  <li>a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and</li>
  <li>a stack</li>
  </ol>
  
  <p>In "Hopcroft/Ullman (1979) <em>Introduction to Automata Theory, Languages, and Computation (1st ed.)</em> we find:</p>
  
  <p><strong>Theorem 14.1</strong> The following are equivalent for $S(n)\geq\log n$.</p>
  
  <ol>
  <li>$L$ is accepted by a deterministic $S(n)$-AuxPDA</li>
  <li>$L$ is accepted by a nondeterministic $S(n)$-AuxPDA</li>
  <li>$L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.</li>
  </ol>
  
  <p>with the surprising:</p>
  
  <p><strong>Corollary</strong> $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.</p>
</blockquote>

CC BY-SA 3.0
2016-05-15T02:27:31.463Z
Thank, Thomas, this is also a natural restriction.
Joseph O'Rourke
CC BY-SA 3.0
2016-05-12T22:43:09.647Z
2016-05-12T22:43:09.647Z
2017-04-13T12:48:30.830Z
Thomas Klimpel
<p>the phrasing of this question is slightly problematic because a Turing machine with a finite tape is arguably not much related to a Turing machine and closer to/ essentially a finite state machine. similarly with all other "restrictions" on Turing machines, almost any restriction seems to be a totally different phenomenon (ie other than Turing completeness with completely different properties). in fact some papers now call out/ study this boundary in detail and it may have some rough similarity with another famous computing boundary ie NP complete phase transitions.</p>

<p>and its somewhat counterintuitive that "computationally simpler/ fully decidable" FSM theory emerged long after the invention of the Turing machine, presumably somewhat loosely inspired by it. so maybe one way to rephrase it is to ask for "most sophisticated decidable models" of computation or "study of the boundary between undecidable and decidable computing models". </p>

<p>so anyway then slightly reformulated in this way, a reasonable answer/ theory/ research program not yet listed is the now significantly developed and actively researched/ advancing theory of <em>timed automata</em> which just won a Church prize for Alur / Dill. heres an example of a paper on timed automata and the study of the computation model (un)decidability boundary and there are many others in this vein.</p>

<ul>
<li><p><a href="http://www.cs.ox.ac.uk/james.worrell/channel.pdf" rel="nofollow">Decidability and Complexity Results for Timed Automata via Channel Machines</a> / Abdulla, Deneux, Worrell</p></li>
<li><p><a href="http://siglog.hosting.acm.org/the-alonzo-church-award-for-outstanding-contributions-to-logic-and-computation/" rel="nofollow">2016 Alonzo Church award, Timed Automata, Alur / Dill</a></p></li>
<li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1093" rel="nofollow">A Theory of Timed Automata</a> / Alur, Dill</p></li>
<li><p><a href="http://processalgebra.blogspot.com/2016/05/interview-with-rajeev-alur-and-david.html" rel="nofollow">Interview with Rajeev Alur and David Dill, recipients of the 2016 Alonzo Church Award</a> / Aceto, Process Algebra Diary</p></li>
</ul>

CC BY-SA 3.0
2016-05-15T21:07:40.973Z
coincidentally the question seems quite conceptually similar to this one recently asked on [cs.se]: [What are the most expressive, terminating languages?](http://cs.stackexchange.com/questions/57015/what-are-the-most-expressive-terminating-languages)
vzn
CC BY-SA 3.0
2016-05-15T23:33:30.640Z
Thanks for the links to *timed automata*, a concept of which I was unaware.
Joseph O'Rourke
CC BY-SA 3.0
2016-05-16T04:44:37.480Z
btw, afterthought/ addendum: one aspect of known theory that tends/ seems to push against any "natural decidable relaxation" of a TM existing, [Rices thm](https://en..wikipedia.org/wiki/Rice%27s_theorem). however another natural pov/ idea somewhat evoked in other answers is that the entire time/ space hierarchy and complexity classes are all the "natural" decidable versions of TMs.
vzn
CC BY-SA 3.0
2016-05-16T17:11:07.963Z
A finite state machine might be too far from a Turing machine to talk of a restriction, but a restricted Turing machine which could compute all primitive recursive functions would be sufficiently close that one can reasonably say it is a restricted model of a Turing machine.
Thomas Klimpel
CC BY-SA 3.0
2016-05-15T20:49:14.063Z
2016-05-15T20:49:14.063Z
vzn
<p>A fairly natural and studied variation is the <em>Tape-Reversal Bounded Turing machine</em> (the number of tape-reversals are bounded); see for example:</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/S0022000068800273">Juris Hartmanis: Tape-Reversal Bounded Turing Machine Computations. J. Comput. Syst. Sci. 2(2): 117-135 (1968)</a></p>

<p><br><strong>Edit</strong>: [this variation is more artificial] the halting problem is decidable for a <em>Non-erasing Turing machine</em> that has <em>at most two left instructions</em> on alphabet $\{0,1\}$; see <a href="http://dx.doi.org/10.1016/0304-3975(94)90038-8">Maurice Margenstern: Nonerasing Turing Machines: A Frontier Between a Decidable Halting Problem and Universality. Theor. Comput. Sci. 129(2): 419-424 (1994)</a></p>

CC BY-SA 3.0
2016-05-12T19:22:25.857Z
The tape-reversal bound is indeed quite natural. Thanks!
Joseph O'Rourke
CC BY-SA 3.0
2016-05-12T13:32:40.600Z
2016-05-12T14:57:25.147Z
2016-05-12T14:57:25.147Z
Marzio De Biasi
<p>If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$),
then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the number of states $Q$, and $S$, and the alphabet
size), a configuration must be repeated.</p>

<blockquote>
  <p>Are there other natural Turing Machine restrictions that render halting decidable?</p>
</blockquote>

<p>Certainly if the state-transition graph has no loops or cycles, halting is decidable. Any others?</p>

CC BY-SA 3.0
2016-05-12T22:47:13.073Z
You can also consider TM which can be proven to be total in say PA, ZFC, ...
Kaveh
CC BY-SA 3.0
2016-05-12T23:05:07.483Z
@Kaveh: Could that be phrased as a restriction on the TM's behavior, in some almost physical sense?
Joseph O'Rourke
CC BY-SA 3.0
2016-05-13T00:07:17.777Z
No, I don't think so.
Kaveh
CC BY-SA 3.0
2016-05-13T00:18:13.400Z
The decision problem on a single-register machine (with instructions unconditional increment-and-jump, if-zero-then-jump-else-decrement-and-jump, and halt) is decidable.
wchargin
CC BY-SA 3.0
2016-05-13T13:16:16.973Z
AFAIK The halting problem for Turing Machines with a bounded space S, is not decidable by Turing Machines that are bounded to space S.
Taemyr
<turing-machines><decidability>
Turing Machine restrictions that render halting decidable
Joseph O'Rourke
# Turing Machine restrictions that render halting decidable

(Asked by: username_0 on 2016-05-12)

If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$),
then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the number of states $Q$, and $S$, and the alphabet
size), a configuration must be repeated.

> Are there other natural Turing Machine restrictions that render halting decidable?

Certainly if the state-transition graph has no loops or cycles, halting is decidable. Any others?

**Tags:** turing-machines, decidability

> **Comments:**
> **username_1**: You can also consider TM which can be proven to be total in say PA, ZFC, ...  
> **username_0**: @username_1: Could that be phrased as a restriction on the TM's behavior, in some almost physical sense?  
> **username_1**: No, I don't think so.  
> **username_2**: The decision problem on a single-register machine (with instructions unconditional increment-and-jump, if-zero-then-jump-else-decrement-and-jump, and halt) is decidable.  
> **username_3**: AFAIK The halting problem for Turing Machines with a bounded space S, is not decidable by Turing Machines that are bounded to space S.  

---

## 3 answers

### Answer by username_6 on 2016-05-12. Score: 31 | Accepted answer

A fairly natural and studied variation is the *Tape-Reversal Bounded Turing machine* (the number of tape-reversals are bounded); see for example:

[Juris Hartmanis: Tape-Reversal Bounded Turing Machine Computations. J. Comput. Syst. Sci. 2(2): 117-135 (1968)](http://www.sciencedirect.com/science/article/pii/S0022000068800273)

**Edit**: [this variation is more artificial] the halting problem is decidable for a *Non-erasing Turing machine* that has *at most two left instructions* on alphabet $\{0,1\}$; see [Maurice Margenstern: Nonerasing Turing Machines: A Frontier Between a Decidable Halting Problem and Universality. Theor. Comput. Sci. 129(2): 419-424 (1994)](http://dx.doi.org/10.1016/0304-3975(94)90038-8)

> **Comments:**
> **username_0**: The tape-reversal bound is indeed quite natural. Thanks!  

---

### Answer by username_4 on 2016-05-12. Score: 19

Considering how parameter passing to subroutines and a huge part of memory management in mainstream computer languages is stack based, an obvious and natural variation is to restrict the unbounded memory of a Turing machine to be a stack.

Such a [model has nice properties](https://cs.stackexchange.com/questions/43152/smallest-class-of-automata-model-whose-corresponding-language-class-contains-cfl/43154#43154), in addition to halting being decidable (well known for *PDA*s):

> The notion of a *PDA* can be generalized to an *$S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA)*. It consists of
>
> 1. a read-only input tape, surrounded by endmarkers,
> 2. a finite state control,
> 3. a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
> 4. a stack
>
> In "Hopcroft/Ullman (1979) *Introduction to Automata Theory, Languages, and Computation (1st ed.)* we find:
>
> **Theorem 14.1** The following are equivalent for $S(n)\geq\log n$.
>
> 1. $L$ is accepted by a deterministic $S(n)$-AuxPDA
> 2. $L$ is accepted by a nondeterministic $S(n)$-AuxPDA
> 3. $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.
>
> with the surprising:
>
> **Corollary** $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.

> **Comments:**
> **username_0**: Thank, Thomas, this is also a natural restriction.  

---

### Answer by username_5 on 2016-05-15. Score: 3

the phrasing of this question is slightly problematic because a Turing machine with a finite tape is arguably not much related to a Turing machine and closer to/ essentially a finite state machine. similarly with all other "restrictions" on Turing machines, almost any restriction seems to be a totally different phenomenon (ie other than Turing completeness with completely different properties). in fact some papers now call out/ study this boundary in detail and it may have some rough similarity with another famous computing boundary ie NP complete phase transitions.

and its somewhat counterintuitive that "computationally simpler/ fully decidable" FSM theory emerged long after the invention of the Turing machine, presumably somewhat loosely inspired by it. so maybe one way to rephrase it is to ask for "most sophisticated decidable models" of computation or "study of the boundary between undecidable and decidable computing models".

so anyway then slightly reformulated in this way, a reasonable answer/ theory/ research program not yet listed is the now significantly developed and actively researched/ advancing theory of *timed automata* which just won a Church prize for Alur / Dill. heres an example of a paper on timed automata and the study of the computation model (un)decidability boundary and there are many others in this vein.

* [Decidability and Complexity Results for Timed Automata via Channel Machines](http://www.cs.ox.ac.uk/james.worrell/channel.pdf) / Abdulla, Deneux, Worrell
* [2016 Alonzo Church award, Timed Automata, Alur / Dill](http://siglog.hosting.acm.org/the-alonzo-church-award-for-outstanding-contributions-to-logic-and-computation/)
* [A Theory of Timed Automata](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1093) / Alur, Dill
* [Interview with Rajeev Alur and David Dill, recipients of the 2016 Alonzo Church Award](http://processalgebra.blogspot.com/2016/05/interview-with-rajeev-alur-and-david.html) / Aceto, Process Algebra Diary

> **Comments:**
> **username_5**: coincidentally the question seems quite conceptually similar to this one recently asked on [cs.se]: [What are the most expressive, terminating languages?](http://cs.stackexchange.com/questions/57015/what-are-the-most-expressive-terminating-languages)  
> **username_0**: Thanks for the links to *timed automata*, a concept of which I was unaware.  
> **username_5**: btw, afterthought/ addendum: one aspect of known theory that tends/ seems to push against any "natural decidable relaxation" of a TM existing, [Rices thm](https://en..wikipedia.org/wiki/Rice%27s_theorem). however another natural pov/ idea somewhat evoked in other answers is that the entire time/ space hierarchy and complexity classes are all the "natural" decidable versions of TMs.  
> **username_4**: A finite state machine might be too far from a Turing machine to talk of a restriction, but a restricted Turing machine which could compute all primitive recursive functions would be sufficiently close that one can reasonably say it is a restricted model of a Turing machine.  

---

