>>joelg+(OP)
One of my earliest exposures to CS was his Computation: Finite and Infinite Machines.
"Communication with Alien Intelligence" is another favorite of mine. The idea of enumerating all possible Turing Machines and looking for ones that do something meaningful is brilliant.
>>gshube+rd
Very true, but FWIW, it's not too hard to find a copy, whether it's a used dead-tree copy (18 or more available on Amazon.com right now), or a bootleg PDF. The PDF version is on the popular e-book sharing sites.