[rstuart4133]

> This is a really nice explanation of decidability.

I'm not an enthused about it as you. It doesn't mention that every undecidabilty involves an infinity. What makes a problem undecidable is not that you can't write an algorithm for it, it's that you can't guarantee the spits out an answer in a finite number of steps.

Take the halting problem. He defines it as "does [the Turning] machine M halt on input i?". The answer is famously no. But you can write an algorithm for it, and if you restrict the Turning machine it's analyzing to having a finite tape it will always spit out the correct answer. The problem is the algorithm creates a power set of the Turning machine states. If you run it on a machine with infinite states it potentially needs to construct power set of an infinity. That's not just an infinity, its a new, distinguishable from, and in some sense higher order infinity than the one you started with.

I can't call an explanation nice when it omits the central idea that explains what is going on under the hood. His description of the universality Turning machines on the other hand was nice.

[lo0dot0]

Even if you can not compute the result in a finite number of steps through the naive approach there could still be a better approach, let me call it shortcut, for determining the value that can be computed. E.g. the geometric series result is known (a/(1-r)) but not computable through evaluating the series itself. A problem is undecidable if you can prove that the shortcut can not exist, it is decidable if you know a shortcut exists (knowing the formula is not required), and potentially either decidable or undecidable if a proof in either direction is unknown.