Sridhar Vembu’s Blog

Wolfram states in his Principle of Computational Equivalence

I believe Wolfram’s book A New Kind of Science contains profound insights, in spite of the fact that the author repeatedly hits you on the head with how profound his insights are.

The basic premise is that every real world system is equivalent to a computer program. One corollary to Wolfram’s principle, which he also talks about in his book, is that most problems arising in nature are formally undecidable. Think of real world questions like “Is this face is beautiful?” or “Will this product succeed in the marketplace?” I believe most such questions are formally undecidable, meaning there is no deterministic computer program that can provide correct answers all the time. The issue is not simply the imprecise nature of the definition of words like “beautiful” or “succeed”. Even if precise definitions can be made, the problems will remain undecidable. The key reason is self-reference: at some level, the definition of beauty can only be made against a definition of “normal” or “plain” or “ugly”, which basically means beauty will refer to itself.

Isn’t there a contradiction here? We say real world systems are equivalent to computer programs, but we also say that no computer programs can exist to give always correct answers to questions? There is no contradiction. The real world system is equivalent to a computer program, but no computer program exists to give an always correct answer about that real-world-equivalent-computer-program. To put it differently, the only way to get answers about the real world is to run the real-world-equivalent-computer-program i.e experience life itself! Wolfram points out the triump of experimental science (just run the experiment, don’t just sit and theorize) this corollary implies.

The always-correct part above is important. It is possible to develop programs that give mostly-correct answers. For example, a face recognition program, like the one developed by Riya could aim to provide mostly correct answer to “Is this face beautiful”, under commonly accepted notions of beauty. The program will make occasional errors, but as long as the errors it makes are similar to the errors humans make, it is OK. The program will pass the Turing Test in mimicking a human being in the judgements it makes.

I have found Wolfram’s Principle and the corollary of formal undecidability very useful. A lot of times, arguments and debates and flame wars we get into are really about formally undecidable questions. Questions like “Is Lisp better than Java” fall in that category - in this case, the self-reference is obvious because both are Turing complete, and so both Lisp and Java can be used to mimic the other. So we have to resort to statistical algorithms to decide it, which means, for example, we select a set of representative programs to code, select a set of representative programmers, select some metrics, and then find results. The only problem, of course, is that every step above will be contested (what is a set of representative programs to code? what is a set of representative programmers?)

The search engine ranking problem is formally undecidable too. The self-reference and feedback looks (ever heard of SEO?) are obvious.

Statistical algorithms, like the ones search engines use, seem like the right answer. But we must never confuse almost-correct with always-correct. This is OK for search engines, but in real life, a lot of insights could be hidden in that gap between almost-correct and always-correct. More on that in a future post.

PS: If it feels I am on a spree of documenting the uncomputable, the undecidable and the unmeasurable, I plead guilty as charged.