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?
A fairly natural and studied variation is the Tape-Reversal Bounded Turing machine (the number of tape-reversals are bounded); see for example:
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)
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, in addition to halting being decidable (well known for PDAs):
The notion of a PDA can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of
- a read-only input tape, surrounded by endmarkers,
- a finite state control,
- a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
- 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$.
- $L$ is accepted by a deterministic $S(n)$-AuxPDA
- $L$ is accepted by a nondeterministic $S(n)$-AuxPDA
- $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.
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 / Abdulla, Deneux, Worrell
A Theory of Timed Automata / Alur, Dill
Interview with Rajeev Alur and David Dill, recipients of the 2016 Alonzo Church Award / Aceto, Process Algebra Diary
