Good Math

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