Turing Completeness Lambda Calculus

[Jim Kata]

I have been kind of trying to teach myself some ideas from CS. What does Turing completeness mean exactly? For example, Lambda Calculus is Turing complete. What does that mean and how do you prove that?

 

[Bill Simpson]

The first sentence of this
http://en.wikipedia.org/wiki/Turing_completeness
defines it:

In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine.

So if you think up some gadget and you want to claim it is Turing complete then you just have to find some way that your gadget can simulate ANY single tape Turing machine.

Sometimes that can take very creative and complicated contortions to accomplish. Sometimes it can be easy, you just show how your gadget and hold a table and a tape and how to simulate the process that the Turing machine would take.

Some very strange constructions have been shown to be equal to Turing machines.

 

[Jim Kata]

Thank you for your response. Could you give an example of a proof, and explain why it proves Turing completeness?

 

[Bill Simpson]

I don't think I have the time to do this in extreme detail, but see if this is enough.

I claim the C programming language is Turing complete.

As evidence of this I show you a skeleton of a program with the data structures that hold the table, the tape, the pointer to the tape, the current state, instructions on how you are to translate your Turing machine into these data structures, a few lines of code which simulate the process of the simulated Turing machine making a transition on the tape, wrap those lines of code inside a loop and the loop terminates when the simulated machine enters the "halt state" in the table.

The next step is always a bit tricky, but I claim it is "obvious" how you can then translate any Turing machine into this bit of code and it is "obvious" how this code will then do exactly what your Turing machine will do.

Thus I claim I have "proven" that the C programming language plus compiler plus hardware is Turing complete.

As with any proof, someone can say that the steps I have given are not sufficiently detailed or that there are flaws and then we try to provide those details or see if there are flaws and see if those flaws can be corrected.

Does this help?

I still have this feeling that we aren't getting to what you really want to know.

 

[LudusRex]

Turing completeness is a concept in computer science that refers to a system's ability to perform any computation that can be done by a Turing machine, a hypothetical computing device that is considered to be the basis of all modern computers. In simpler terms, it means that a system is powerful enough to solve any computational problem that can be solved by a computer.

Lambda calculus is a mathematical model of computation that was developed by Alonzo Church in the 1930s. It is considered to be the foundation of functional programming and has been used as a basis for many programming languages, such as Lisp and Haskell. One of the key characteristics of lambda calculus is its ability to define and manipulate functions, making it a powerful tool for solving computational problems.

To prove that lambda calculus is Turing complete, we need to show that it can simulate a Turing machine. This can be done by constructing a function in lambda calculus that can take as input a description of a Turing machine and its input, and then output the result of the computation performed by the Turing machine. This shows that lambda calculus has the same computational power as a Turing machine, and therefore it is Turing complete.

In conclusion, Turing completeness is a fundamental concept in computer science that signifies a system's ability to solve any computational problem. Lambda calculus is an example of a Turing complete system, and its ability to simulate a Turing machine can be proven through a construction that shows its computational equivalence.