> A patent covering an invention with source code in C would presumably also extend to the same invention if implemented in Prolog.
Strictly speaking, if the patent covers an invention in C it does not cover much else (doctrine of equivalence makes this a bit more complex). Still such a patent would be bizarre. What is normal practice is to describe an exemplary embodiment in for instance C but make clear that this is not limited to C. The scope of protection is determined by the claims and the claims should not refer to a single specific embodiment.
> An invention does not have to actually work in order to be patentable.
Are you really sure about this? I am not.
> pretty much anything can be patented without having to give a demonstration
This is not the same thing. In pharmaceutical patent prosecution you can apply for a patent for a drug but you will normally have to demonstrate the drug has the effect you claim it has.
> it is up to the patent office to prove that an invention does not in fact work
Some times, yes. And this is why examiners hate perpetual motion machines in certain jurisdiction since the examiner has to demonstrate why it cannot work and so so without referring to the thermodynamic law that energy cannot be created, only transformed. And some of these inventors can be rather clever.