I'm currently teaching our intro course on Theoretical Computer Science to first-year students, and I came up with the following simple proof that there are non-computable functions from N->N:
It's a simple cardinality-based argument. The set of programs in any arbitrary language is countable - just enumerate by length-lexicographic order (shortest programs first, ASCIIbetically for programs of equal length). The set of functions from N->N is uncountable (as the powerset of N is uncountable - in a pinch by a diagonalization argument - and hence the set of indicator functions alone is uncountable). So there are more functions than programs. Hence there are functions not computed by any program, hence non-computable functions.
My question: This is so simple that either it should be well-known or that it has a fatal flaw I have overlooked. In the first case, can someone point me to a suitable reference? In the second: What is the flaw?
Thanks. Yes, I use the Church/Turing hypothesis/definition of computable (with any Turing-complete language, though programs for UTM are most traditional). OK, I see why I need the Axiom of Choice. I don't think I need the powerset axiom - that's just a convenient shortcut. And yes, it's not a constructive proof.
- Badges
- Science method
- Similar topics
- Teaching