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.)
Latest Answers