Turing Completeness Lambda Calculus


by Jim Kata
Tags: calculus, completeness, lambda, turing
Jim Kata
Jim Kata is offline
#1
Jun18-13, 03:33 PM
Jim Kata's Avatar
P: 233
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?
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
Bill Simpson
Bill Simpson is offline
#2
Jun18-13, 10:49 PM
P: 972
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
Jim Kata is offline
#3
Jun19-13, 02:39 PM
Jim Kata's Avatar
P: 233
Thank you for your response. Could you give an example of a proof, and explain why it proves Turing completeness?

Bill Simpson
Bill Simpson is offline
#4
Jun20-13, 12:53 AM
P: 972

Turing Completeness Lambda Calculus


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.


Register to reply

Related Discussions
Simply Typed Lambda Calculus question - Beta Reduction Calculus & Beyond Homework 1
Any Lambda Calculus Expert Out here? Engineering, Comp Sci, & Technology Homework 0
Lambda Calculus Semantics Set Theory, Logic, Probability, Statistics 6
Lambda calculus: fold & Y Calculus & Beyond Homework 0
lambda calculus normal form Calculus 2