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.