I think the degree-inflation problem is the key here. There is no reason why a person needs a degree to be able to program. That wasn't the original purpose of such degrees.
In a nutshell, academic certifications assess whether you know things, while industry certifications assess whether you can do things.
For a business, there is a strong focus on doing, rather than knowing. Who cares about whether certain classes of problems are computable? Just write a program that does it for our problem set.
And there is nothing wrong with this. At the same time though, if you want to make advances that bring about the next generation of programming/technology/etc, you would need to have an understanding of how these things work.
Unfortunately, this line has been blurred significantly -- universities have become big business, caring more about selling degrees then teaching fundamentals. At the same time, businesses have been using degrees as a criteria for hiring, and then complaining that people with said degrees can't do what they expect them to.
I hate to describe a problem without providing a solution, but I don't really have a solution for this.