What does “turing complete” mean in computer science?
In: Engineering
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.
Latest Answers