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?

Solution 1:

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.

Solution 2:

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).

Solution 3:

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.