Wolfram's A New Kind of Science is execrable. It's 1100 pages based on a point that everyone interested in the subject already knew: simple cellular automata can have arbitrarily complex behavior. Given that CAs and Turing Machines are the particle accelerators of computer science, and given the heavy buzz related to algorithmic thermodynamics, and given Wolfram's claims, a reasonable expectation of this book is that the "new kind of science" might, oh I don't know, consist of something more than 1100 pages of "Look at the pictures and you'll develop an intuition that I'm a genius." Instead, Wolfram seems to think that the generation of complex sequences from simple rules is some kind of shattering revelation. At first, you think "Okay, maybe I'm missing something," but there's no there there. It's as if Wolfram had never heard of complex numbers, had never heard of pi (which can also be generated from a simple formula).
For a much better popular book on the deep relationship between computer science and physics, try Fire In The Mind. For something meatier, I like Complexity, Entropy and the Physics of Information: The Proceedings of the 1988 Workshop on Complexity, Entropy, and the Physics of Information.