O'Reilly logo

Good Math by Mark C. Chu-Carroll

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

23Pathology and the Heart of Computing

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required