Algorithmics - the spirit of computing
That's the name of the book which I got today; and I feel this is one theory book which I might be able to read and understand at least a little bit. It goes into some deep issues (computability and complexity) without resorting to heavy-duty math and at the same time, not watering down stuff "dummies" style. This is something which only a true master can do! The book has a chapter on the "correctness" of algorithms. The author raises an interesting issue towards the end of that chapter. Sophisticated computer programs are being used to prove results in pure math these days (he gives the example of the four-colour theorem). Are these proofs really valid - given the fact that the programs themselves are seldom *proved* to be correct. And, even if the programs are verified (note that the term "verified" is being used in a strict mathematical sense), what about the compiler which translates the program to assembly code (anybody wants to prove the correctness of GCC?). What about the assembler, linker, loader (part of the OS)? And, what about the hardware?