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?

  • 1
    You can also consider TM which can be proven to be total in say PA, ZFC, ... – Kaveh May 12 '16 at 22:47
  • @Kaveh: Could that be phrased as a restriction on the TM's behavior, in some almost physical sense? – Joseph O'Rourke May 12 '16 at 23:05
  • No, I don't think so. – Kaveh May 13 '16 at 0:07
  • 1
    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 May 13 '16 at 0:18
  • 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 May 13 '16 at 13:16
up vote 31 down vote accepted

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)


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)

  • The tape-reversal bound is indeed quite natural. Thanks! – Joseph O'Rourke May 12 '16 at 19:22

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

  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.

  • Thank, Thomas, this is also a natural restriction. – Joseph O'Rourke May 15 '16 at 2:27

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.

  • coincidentally the question seems quite conceptually similar to this one recently asked on Computer Science: What are the most expressive, terminating languages? – vzn May 15 '16 at 21:07
  • 1
    Thanks for the links to timed automata, a concept of which I was unaware. – Joseph O'Rourke May 15 '16 at 23:33
  • btw, afterthought/ addendum: one aspect of known theory that tends/ seems to push against any "natural decidable relaxation" of a TM existing, Rices thm. 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 May 16 '16 at 4:44
  • 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 May 16 '16 at 17:11

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.