Problem teaching computability I have difficulty teaching the concept of computable functions. I tried to develop the idea of why researchers like Hilbert/Ackermann/Godel/Turing/Church/... invented the notion of 'computability'. The students immediately asked: "what does computability mean?" and I can't answer unless I teach them Turing machines, and then answer "a function is computable if a Turing machine computes it."

So,


  Is there a description of computability which does not require resorting to Turing machines, λ-calculus, or similar models of computation? Even an intuitive description will suffice.
75 years ago there were no computers around. So one had to explain very carefully the mathematical idea of a computer.

Today everybody knows what a computer is, and is probably carrying one around most of the time. This can be used very successfully in teaching because you can skip the rather outdated idea of a machine with a tape. I mean, who uses a tape? (I know, I know, you feel insulted and Turing was a great man and all that, and I agree with you).

You just walk into the class and ask: so it there anything your iPhones can't compute? This immediately gets you into questions about bounded resources. Then you say: well suppose your machine actually had unlimited memory, is there anything it couldn't compute? And you idealize a bit more and limit attention to number-theoretic functions (because you are not interested in Facebook at the moment). You'll have to explain a bit how computers work (as mentioned in the comments, it's good if the students know a programming language because you can use that instead of describing hardware), but after that you can use all the classical arguments of computability theory to derive results. It doesn't matter that your students' mental picture of a machine is iPhone. In fact, it matters: it makes it easier and more relevant for them to know that their iPhone can't do certain things.