What does “turing complete” mean in computer science?
In: Engineering
A machine is Turing complete when it can figure out anything a modern computer could figure out. (The set of things computers can figure out hasn’t been growing over time as far as computer scientists are concerned. They have just been getting faster, and we have been getting better at programming them to do things.)
The term refers to a Turing Machine. A Turing machine is a theoretical kind of computer. In practical terms it isn’t a very useful computer. On the off chance someone builds one, they generally do it for the novelty.
In theoretical terms, a Turing machine is the only computer you need. When you look at what a Turing machine does, it is hard to imagine it could do anything even remotely like a modern computer could. However, computer scientists have developed techniques for programming the Turing machine that can be thought of like building blocks – ways you can program the machine that can be re-used over and over. Whatever you figure out how to do, you can pretend the machine can just do that for you without having to think about it again. The computer gets “new features” as soon as you can figure out how to do something in a repeatable way. Eventually you could work your way up to a modern computer’s capability (in theory. In physical terms any way of building a Turing machine couldn’t match the speed of modern computers.)
It means that something is capable of computing things / running programs that can be run by other computer programming languages.
Alan Turing proposed a model of a very simple computing machine – what we now call a Turing machine – that could only read or write one symbol at a time, and move left or right one space at a time, on some long tape that it would use as its memory. He showed that this incredibly simple, limited machine was capable of computing anything that could be done with any programming language – calculating Pi, playing Chess, etc.
What this essentially means is that all programming languages are equally capable. Some may be faster than others, but if something can be computed by one, it can be computed by any other.
A few computer languages are not Turing complete. A classic example is that regular expressions are not Turing-complete – you can use them to solve only certain problems. But nobody would call regular expressions a programming language. Any actual programming language is Turing-complete.
What’s surprising is when things that don’t even seem like programming languages turn out to be Turing-complete.
As an example, Minecraft is Turing-complete. You can make blocks that do something based on the configuration of other blocks, and put things together in just the right way to make a “program”, and in fact many people have done this.
A more curious example is that Minesweeper is Turing-complete. This one is more abstract – if I understand that one correctly, given a large enough board, you could encode the computation you want solved in such a way that “playing Minesweeper”, i.e. perfectly solving the board and determining all of the possible configurations of bombs, would be equivalent to solving the desired computation.
A Turing machine is the most complete machine, if something is computable it can be done by a Turing machine.
A Turing complete machine is a machine who can make the same as a Turing Machine. The cellphone in which I write this, the computer you have, they are Turing complete models.
An finite automaton it’s not, it can’t recognise palindromes, for example.
Latest Answers