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

To Halt or Not To Halt?

To begin, we need to define what a computing device is. In formal mathematical terms, we don’t care how it works; all we care about is what it can do in abstract terms. So we define something called an effective computing device or an effective computing system, abbreviated ECS. An effective computing device is any Turing-equivalent computing device: it could be a Turing machine or a λ calculus evaluator or a Brainf*** interpreter or the CPU in your mobile phone. I’m being deliberately vague here because we don’t care what kind of machine it is. What we want to show is that for any possible computing device, it won’t be able to tell correctly whether programs halt.

An ECS is modeled as a two-parameter function:

The ...

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