4 ms·

This seems inspired by Cantor's infinity proof. I've seen a halting problem proof via Cantor's diagonal as well... Are there any other significant proofs that

This seems inspired by Cantor's infinity proof. I've seen a halting problem proof via Cantor's diagonal as well... Are there any other significant proofs that use a similar methodology? Why does Cantor's method work well here? ...algorithms / programs are countably infinite, no? (Finding this more interesting now than I did in school!)

pacifist 9y ago
Yes, Godel used Cantor's method of diagonalization in his proof. Turing also used it on the halting problem. Penrose talks about this in "The Emperor's New Mind." Cantor rocked the Casbah. Smart people saw it and used it.
dvt 9y ago
> Why does Cantor's method work well here? ...algorithms / programs are countably infinite, no? It seems that A (computable functions that take an integer and return 0 or 1) are countably infinite but Q (all functions that take an integer and return 0 or 1) are uncountably infinite. As it turns out, there's a lot more stuff that we can't prove than stuff we can.