what is turing complete ?
what is turing complete ?
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.
The Concept Turing Completenes is named after mathematician and computer scientist Alan Turing.
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 Turing machine.
But my favourite answer for that Question is written in Eli5:
Imagine you have some words: "fish", "orange", "racecar", "twelve", "jeep", "game", "rotator". What would you do if I asked you to tell me which of the words are exactly 4 letters long? Maybe you would start at the beginning of each word and count the letters, one at a time. In the end, you find that "fish", "jeep", and "game" all have exactly 4 letters. None of the other words have four letters. This is a pretty simple question because you only have to think about one thing: the number of letters you have counted. And you never have to count higher than 4 (if you get to 5, the word is already too long).
Now, which of the words look the same forwards and backwards? This is a little harder. One way to do it is to read out each word forward and remember what it looks like and then read it out backwards and see if it looks the same. Only two of the words, "racecar" and "rotator" are the same forwards and backwards.
Why is this second question harder than the first question? In the first question you only had to remember the number of letters and you only had to count as high as 4. In the second question you had to remember all the letters (or maybe you had to run your eyes back and forth over the words checking each letter separately). If the words were really long, you would have had to remember a lot of letters to answer the question or you would have had to go back and forth a lot of times.
Now lets look at a more interesting list: "22 = 6", "52 = 25", "31 = 7", "23 = 8". Which of these equations are correct? After looking at each of them, it looks like it is just "52 = 25" and "23 = 8". This problem looks like it is even harder than the other two. You have to keep the first number in your head, then you have to keep the second number in your head and make sure to multiply the first number by itself the correct number of times. To top it all off, you have to keep the third number in your head to make sure it is correct. This is a lot of stuff to remember. Imagine if the numbers were really large. This problem might get too hard to do in your head pretty fast.
So far we have looked at different problems. It looks like some are harder to do than others--they require more remembering or more moving around with your eyes or just more complicated patterns like exponents. It turns out this isn't just true for people, but also machines.
There are some machines that are so simple they can only answer questions like the first question about length. There are other machines that can only answer the second question. To make it easier to talk about these machines, they can be put into groups based on what kinds of rules they have inside them. Some machines only have rules that let them go from one letter to the next and never look back. Other machines have rules that look back but only in the same order that they saw the letters.
There is a certain kind of machine, called a Turing Machine, that has rules that let it look over the word in any order and even write things down to help it remember things. This kind of machine is special because even though it has very simple rules, these rules can be used to make a machine for every question that other machines can solve. If they can answer it, there is a Turing Machine using just the Turing Machine rules that can also answer it.
Now, this very simple special kind of machine is not so special that it is the only kind of machine that can answer all the questions. There are other kinds of machines that can answer all the questions that the Turing Machines can answer. Maybe they have all the rules that the Turing Machines have and some other rules. Maybe they have very different rules that don't look at all like the Turing Machine rules. The RULES that make up these machines are Turing Complete. This means that you can make machines with just these rules to answer all the questions that Turing Machines can answer. And remember, Turing Machines can answer ALL the questions that any machines can answer. This means that Turing Complete rules can also be used to answer all the questions that any machine with any set of rules can answer.
So if you have a question that has an answer and you have a Turing Complete set of rules, you can make a machine to answer that question no matter what it is or how hard it is.
This is really important, because people don't want to learn lots of different sets of rules for different problems. If you had to learn one set of rules for making machines that could count letters and another set of rules for making machines that could check for palindromes, making new machines for new problems would be really hard. Instead, if you have rules that are Turing Complete you know that you have don't need to learn any other rules to solve a problem: you already have a full toolbox. This means we can be much more productive at making machines than we would be without Turing Complete sets of rules!