What is Turing Complete?
What does the expression "Turing Complete" mean?
Can you give a simple explanation, without going into too many theoretical details?
Here's the briefest explanation:
A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory).
So, if somebody says "my new thing is Turing Complete" that means in principle (although often not in practice) it could be used to solve any computation problem.
Sometime's it's a joke... a guy wrote a Turing Machine simulator in vi, so it's possible to say that vi is the only computational engine ever needed in the world.
Here is the simplest explanation
Alan Turing created a machine that can take a program and run that program and show some result. But then he had to create different machines for different programs. So he created "Universal Turing Machine" that can take ANY program and run it.
Programming languages are similar to those machines (although virtual). They take programs and run them. Now, a programing language is called "Turing complete", if that it can run any program(irrespective of the language) that a Turing machine can run given enough time and memory.
For example: Let's say there is a program that takes 10 numbers and adds them. Turing machine can easily run this program. But now imagine for some reason your programming language can't do the same addition then it's Turing machine incomplete. On the other hand, if it can run any program like the universal turing machine can run, then it's Turing complete.
Most modern programming languages like Java, JavaScript, Perl etc are all turing complete because they all implement all the features required to run programs like addition, multiplication, if-else condition, return statements, ways to store/retrieve/erase data and so on.
Update: You can learn more on my blog post: "JavaScript Is Turing Complete" — Explained
From wikipedia:
Turing completeness, named after Alan Turing, is significant in that every plausible design for a computing device so far advanced can be emulated by a universal Turing machine — an observation that has become known as the Church-Turing thesis. Thus, a machine that can act as a universal Turing machine can, in principle, perform any calculation that any other programmable computer is capable of. However, this has nothing to do with the effort required to write a program for the machine, the time it may take for the machine to perform the calculation, or any abilities the machine may possess that are unrelated to computation.
While truly Turing-complete machines are very likely physically impossible, as they require unlimited storage, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had unlimited storage. All modern computers are Turing-complete in this sense.
I don't know how you can be more non-technical than that except by saying "turing complete means 'able to answer computable problem given enough time and space'".
链接地址: http://www.djcxy.com/p/22902.html上一篇: 函数式编程与声明式编程VS势在必行的编程
下一篇: 什么是图灵完成？