# How to Prove a Programming Language is Turing Complete?

I had some thoughts about how to prove the turing completeness of a programming language. I came to the conclusion, that if you could write a program that is able to parse a turing machine program, both should be equivalent as you could execute every turing machine program with that parser written in that language. Therefore the language must be turing complete. Am I right? What are other ways of proving turing completeness?

• It looks as if you've largely answered your own question. Besides Turing machines there are recursive functions and various other models of computability known to be equivalent to Turing machines. Put any of those in the role of Turing machines and do the same argument and you've got it. Or take any other programming language known to be Turing-complete and show that you can emulate that within your language. – Michael Hardy Feb 22 '12 at 17:22
• You don't really need to parse a Turing machine description, you just have to show how to simulate one, and you can even restrict the simulated machine a lot – vonbrand May 17 '14 at 10:25

## 3 Answers

A programming language is Turing complete if and only if we can write every computable function in this language. So proving that we can emulate a turing machine is a good way to prove that a language is turing complete, by the way this is not the only way, another way can be to prove that your language is able to describe all the $$\mu$$-recursive functions. To do that you just have to prove that you can write some programs that compute some special functions (the constant zero function, the successor operation and the projection functions) and shows that you can write the operations of composition of functions and $$\mu$$-recursion (i.e. minimization) and primitive recursion (primitive recursion being a special case of $$\mu$$-recursion this is wrong as Andrej Bauer pointed out in the comments below and explained here) in term of operations of programs.

Hope this helps.

• If I prove it the way I proposed, can we assume that it is also possible for a Turing machine to emulate the system I wrote the simulator in? Is it by definition? Could there be a parser that could not be simulated by a Turing machine? Wouldn't that mean that the parser must not exist as it would not be computable? From my understanding of equivalence I have to also that you'd have to be able to emulate the system in a turing machine, not only the other direction. – bot47 Feb 22 '12 at 17:29
• Your objection is correct, to prove the equivalence you should prove the converse, i.e. that a turing machine or any other equivalent model can "implement your language" (or if you prefer emulate your system). By the way since today there's no computation model that is stronger than Turing machine, infact this is what the Church thesis says (en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis). – Giorgio Mossa Feb 22 '12 at 18:21
• Thanks a lot. As you said a Turing machine is the strongest computation model. In case my system is less strong, it can obviously implemented in a turing machine and a parser for a turing machine could never designed in that system. If it is equally strong, it's "turing equivalent", thus turing complete. If it's even stronger (it's a shame there is no Nobel Prize for Computer Science) it's turing complete, too, since you designed a parser in it in that IS turing complete as it implements a turing machine. In addition to that a stronger model can emulate the weaker ones. Am I right so far? – bot47 Feb 22 '12 at 20:37
• Yes Turing completeness is the requirement that your model of computation is able to simulate every turing machine, or an equivalent model. If you have a strictly stronger computational model then turing machine you could ask for the Turing award which is the equivalent to Nobel Prize for Computer Science. – Giorgio Mossa Feb 22 '12 at 20:45
• @MaxRied, you keep speaking about parsing. However, parsing != simulating, keep that in mind. So you should say simulating instead of parsning. – sxd Feb 23 '12 at 2:33

Parsing is not really correct. I think you wanted to say that if you can simulate a Turing machine in your programming language.

For another method: you could write a program that evaluates all computable lambda calculus expressions. (Or any formal system which is equivalent to Turing machines, e.g. abaci).

Parsing is not to the point, and here is why. The language of all syntactically correct programs in a given language is (or should be) recursive, which is lower on the hierarchy than the languages defined by Turing-complete programming systems, which is recursively enumerable. In fact, for a very simple model (like Turing's original formulation), the language of all syntactically correct "programs" could be as low in the hierarchy as finite-state (regular).

In other words, there is very little relationship between the difficulty of parsing programs (a static kind of task) and simulating/emulating the running of a program (a very dynamic task).

So, as the others here say, you need to show that the programming language/model you want to prove Turing-complete can carry out certain basic operations and can also combine operations to make longer, arbitrarily complex programs.

Then there's the issue of the unlimited storage of theoretical models -- like the two-way unbounded tape of a classical Turing Machine -- versus the practical limitations on storage of real-life programming languages and systems. But that's a subtle topic that is usually not addressed in answering questions like yours, as it bears on a different set of theoretical issues.

• If you insist on the infinite memory, no computer system could ever be Turing-complete, don't they? Assuming Turing Machines are Turing-complete, if I could simulate Turing Machines, would that mean, beside the memory limitation, that the system I used was Turing-complete? – bot47 Feb 22 '12 at 17:15
• Let simply say that a computer has potentially infinite memory, because the memory can be expanded. And yes if you can simulate every Turing machine your system (computation model) is Turing complete. – Giorgio Mossa Feb 22 '12 at 18:26
• Yes, just assuming unbounded memory is one way to deal with it -- for most research purposes or at the undergrad level. But if you want to mathematically address infinite memory in a finite world you can use various topological techniques, with limits etc. But that's grad-level stuff -- topology is the big brother of calculus. – David Lewis Feb 23 '12 at 19:32