Comment 1 for bug 335666

Ugh.

The problem here is that if you execve() a binary whose interpreter is missing, then the kernel just gives you ENOENT. I'm not sure that dropping in stub interpreters for anything that might need to exist is a good solution here.

Maybe this would be better fixed at the command-not-found level. It could check whether the binary is actually present on $PATH, and then hunt around to tell you which package you need to install in order to get hold of its interpreter.