How does one prove that a programming language is not Turing complete?

I know one may attempt to show that every program that could be written in the programming language in question is primitive recursive.

But are there other ways/constructs than primitive recursion that we know are also not as expressive as $\mu$-recursion?

  • 1
    $\begingroup$ More generally, if you can prove that all programs terminate, or even that the halting problem for your language is solvable (and that the language can be implemented effectively), than that implies that it is not complete, even though it may allow some things that are not p.r. -- such as Ackermann's function. $\endgroup$ Commented Oct 15, 2015 at 14:42
  • $\begingroup$ You can prove a general rule about the class of problems your language can solve, like the Pumping Lemma for finite state automata (although, as Henning notes, the pumping lemma is overkill since you can solve the halting problem in that case.) $\endgroup$ Commented Oct 15, 2015 at 15:03
  • $\begingroup$ What can you say about this programming language? Can it express the Ackermann function? $\endgroup$
    – BrianO
    Commented Oct 15, 2015 at 15:49


You must log in to answer this question.

Browse other questions tagged .