I'd say it was "hard" all along. The question of computability is challenging in that it requires a good deal of formalism and theory to get anywhere near probl

I'd say it was "hard" all along. The question of computability is challenging in that it requires a good deal of formalism and theory to get anywhere near problems we deal with every day. Take NP-Complete for instance. We know a problem is NP-Complete if we can do a Karp Reduction from another NP-Complete problem and also prove the problem is in NP. Sure, that's fine. But how was the first NP-Complete bootstrapped? Well, using automata and generalized turning machine languages! You can use NP-Complete as a concept at work, and never touch the original proof using a non-determistic turning machine language. That's at least one course worth of material to teach in order to get students to understand automata. To me: that's a complex approach to a simple question: what can we compute? We have to invent a series of automata with increasing complexity and corresponding theories/proofs. I don't think it's bad, it's just the nature of the problem!