I have to disagree, the field complexity (I don't call it NKS) since I was introduced to it by reading stuff from the sante fe institute is a unifying force across disciplines. The large amount of rules that explain the world today are manifestations of simple rules acting in complex ways so that the findings of today describe the emergent behavior of these simple laws. Cellar automata is just one way of tackling the problem.
Complexity is a wonderful thing and there are many complex phenomena which arise from simple rules. But unless you can make predictions that agree with observation and experimentation... it's not Science. The nexus between Physics and Complexity is very interesting and beautiful, but it's not necessarily very useful. If Physics were "digital", many symmetries would likely be violated, and that can't happen. The discrete world and the continuous world are entirely different beasts, and though I appreciate Wolfram's efforts and his recreational NKS stuff, it's a few millenia away from being a new kind of Science.
"Predictions are nice if you can make them. But the essence of science lies in explanation, laying the bare fundamental mechanisms of nature." -- M. Mitchell Waldrop
I agree. However, how can the fundamental mechanisms of Nature be explained if we do not confront theories with observation and experimentation? Physics is a fortunate field because the beauty of the mathematics is a good indicator of whether a certain theory is correct or not (excluding the Standard Model ;-) but other fields of the Natural Sciences cannot afford that luxury. I don't want to start discussing the Philosophy of Science because I am not qualified for that...
Actually, Quantum Theory states that the world, at the lowest level we currently conceive of, is discrete and 'digital'. Time, space, energy - everything - come in little chunks called quanta which represent the smallest possible subdivision that the universe permits. For example a photon is a quantum of energy - the smallest possible unit of energy. If you had a perfect dimmer switch, that would be the lowest setting - turn it even a fraction more and it's off completely. The universe isn't continuous at all - it just looks like it from waaaay up here where we live. If you zoom in far enough, you can see the pixels of reality. All properties of the universe behave this way, according to our best theories and best abilities to test them.
Given that this applies to space and time too - look up 'plank length' - you can see why this would make people make the connection to cellular automata. Zoom in far enough and quantum theory tells you that space is divided up into minimum sized chunks, and quantum events can only happen within this framework.