Gödel, Escher, Bach by Douglas R. Hofstadter

What it is about:

An accessible and quasi narrative description of the foundations of computing, algorithms and formal representations from Turing's formulation of computation and the halting problem to predicate calculus.

Why it changed my thinking:

Once you start seeing programs and algorithms as constructs that represent knowledge and concepts, like Godël's theorem that encodes predicate calculus in natural numbers, there is no going back, modeling problems in formal terms and using the power of those abstractions to solve them becomes addictive.

Where to get it:

(Note, if you buy from the links here, I get a little commission back)