After teaching my philosophy of cognitive science undegraduates what a Turing machine is, I mentioned that there are functions that can't be computed using a Turing machine. A curious philosophy major asked for an example of such a function. Most of the students in the class are not CS students and need not be mathematically adept, so I am limited as to what I can say, except to those students who want to hear more outside of class.
The only example of a particular function that is uncomputable that I could come up with off the top of my head was the halting problem, but that would have required a substantial digression, and it would seem quite obscure to most of the students if I walked them through it. It would also not be sufficiently useful to explain to the class why there must be uncountably many functions that are not Turing-computable. (First step: teach the countable/uncountable distinction.)
Is there an example of an uncomputable function that's relatively easy to describe and understand--more so than the halting problem?