Patents with source code

If John invents something and starts practicing it, and then Mary produces a patent for the same invention and demands that John stop, but John proves that Mary only dreamed it up and never actually proved it would work, I believe that means Mary didn't invent the thing, so her patent is invalid and John doesn't have to stop.

This is not a realistic scenario. Instead you would invoke the First inventor defence act ...

It wasn't meant to be realistic; it was meant to exemplify a point, which from everything you've said appears to be valid: you can't patent a mere conception. If Mary's patent is based on something she conceived but never reduced to practice, she has no rights in John's invention based on the same idea.

However, I learned something from the section of the Manual of Patent Examining Procedure of the US Patent and Trademark Office that you cited: constructive reduction to practice. (For those not familiar with the legal lingo, "constructive" means fictional -- something the law assumes to be true even if it definitely isn't).

IIUC, constructive reduction to practice can substitute for actual reduction to practice, and consists of simply describing in the patent application how to build the thing and do something useful with it. So no, you don't have to prove it works in order to have invented, and thus to get a patent.

I assume that if it turns out later that the instructions in Mary's patent application don't work, that the entire patent is invalid and Mary doesn't have any rights in the invention even if there's some other way to make use of her idea.