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?

Answer

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 μ-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 μ-recursion (i.e. minimization) and primitive recursion (primitive recursion being a special case of μ-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.

Attribution
Source : Link , Question Author : bot47 , Answer Author : Giorgio Mossa

Leave a Comment