Easy-to-describe example of uncomputable function 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?
A classic example of an uncomputable function is The Busy Beaver Problem: For each N, consider all N-state Turing Machines over the alphabet { [blank], 1 }; over all of those machines which always halt when started on a blank tape, find one which leaves the maximum possible number of 1's on the tape once it has halted; then f(N) is that number of 1's.