
#1
Jun1813, 03:33 PM

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?




#2
Jun1813, 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 datamanipulation 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 singletaped 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. 



#3
Jun1913, 02:39 PM

P: 233

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




#4
Jun2013, 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 