In computer science–speak, we say that a computing system is “Turing complete” if it can do the same computations as a Turing machine. That’s important because the Turing machine is an example of the maximum capability of any mechanical computer. The capability of a Turing machine can be matched, but never exceeded. If a computing device can do the same computations as a Turing machine, then it can do everything that any computer can do. Understanding that, we’d like to understand what a machine needs to be Turing complete. How hard is it to make machines that can perform any possible computation?

The answer is, surprisingly easy.

Computers can do amazingly complicated things, and because of that, we ...

Start Free Trial

No credit card required