Does the incomputability of kolmogorov complexity imply that we will never have a final theory of everything?

Question

The Kolmogorov Complexity is the size of the simplest program that produces a specific output. By the Curry-Howard Correspondence, "programs" are isomorphic to "axiomatic systems" and "outputs" are isomorphic to "entailments". Since the size of the smallest system that is consistent with all prior observations is not Turing computable, we also don't know the contents of the smallest system (proof is by contradiction).

One can view the job of scientists as to develop the simplest possible axiomatic system that is consistent with all prior observations. For example, in celestial mechanics, one might consider the Ptolemeic system where each planet revolves around the earth, but there are cycles in those cycles (see illustration), and cycles in those cycles in those cycles, etc. up to hundreds of cycles on cycles. In principle, a theory like this can be consistent with all prior observations, but it asks us to assume a huge number of parameters as axioms. The Copernican system is far simpler, just having two parameters (radius and radial velocity) for every planet. Kepler simplified this even further by discovering a relationship between the radius and radial velocity. Newton simplified this even further by proving that Kepler's laws do not need to be taken as axioms, but instead can be derived from even simpler axioms (Newton's three laws of motion plus the Law of Universal Gravitation). But the incomputability of Kolmogorov Complexity implies that we will never know if there is a simpler possible explanation of celestial mechanics.

I'm putting this question here and not in computer science or math because the incomputability of Komlogorov Complexity and the validity of the Curry-Howard Correspondence are settled fact. My question is how to apply these facts to the epistemology of science.

1. Are there other views on what science is that don't reduce it to a data compression problem?
2. Can you recommend a text on the philosophy of science that is approachable by non-philosophers?

Answer 1

Let's start with some comments. You say:

I'm putting this question here and not in computer science or math because the incomputability of Komlogorov Complexity and the validity of the Curry-Howard Correspondence are settled fact.

Nothing wrong with questions that ask after philosophy of math, computer science, and physics, especially if they are cross-domain questions. This is the right forum.

One can view the job of scientists as to develop the simplest possible axiomatic system that is consistent with all prior observations. For example, in celestial mechanics, one might consider the Ptolemeic system where each planet revolves around the earth, but there are cycles in those cycles (see illustration), and cycles in those cycles in those cycles, etc. up to hundreds of cycles on cycles. In principle, a theory like this can be consistent with all prior observations, but it asks us to assume a huge number of parameters as axioms...

Epicycles are a famous example from the history of science that recognizes that parsimony is one criterion for choosing among theories when observation leads to underdetermination. A simpler example is underdetermination in linear regression where our observation is a simple set of points.

Are there other views on what science is that don't reduce it to a data compression problem?

Absolutely. One is free to abstract science to the deductive-nomological method or Ramsey sentences and examine them with the tools of mathematical logic or information theory, but obviously the sciences, which use a methodological naturalism including inference to best explanation which when used tightly coupled with philosophical methods (an epistemological flavor known as naturalized epistemology (SEP)) often promote particular philosophical worldviews like physicalism or property dualism. The sciences contribute knowledge to society, broadly, that is applied to solve problems and make predictions. (And I say sciences on account of Popper's problem of demarcation.) And they are a source of cultural inspiration such as works of science fiction. There is far richer understanding in the philosophy of science and the sociology of science than metrics and formal language models.

Can you recommend a text on the philosophy of science that is approachable by non-philosophers?

If you have no texts, then a really quick overview is Introduction to Philosophy of Science by Oxford Press written by Samir Okasha (GB). It's shallow, but it does highlight some important points. My favorite is an out-of-print edition of Blackwell's A Companion to the Philosophy of Science edited by Newton-Smith (GB) which is not the same as their The Blackwell Guide to the Philosophy of Science. The Companion has a series of essays based on terminological topics, all of which were edited with the strategy of integrating them into each other. Other sources include the Stanford Encyclopedia of Philosophy and the Internet Encyclopedia of Philosophy both of which are online and free. There are other's like Encyclopedia of Philosophy and Routlidge's Encyclopedia.

There are primary sources, like works by the logical positivists, history of science texts. Kuhn's The Structure of Scientific Revolution, Hempel's Aspect of Scientific Experience, and Popper's various works that are informative. And Google books has a whole selection of introduction to philosophy of science texts to numerous to recite.

Does the incomputability of kolmogorov complexity imply that we will never have a final theory of everything?

Well, and lastly we get to what Carnap hated about philosophical questions: meaningless terminology that constituted fodder for metaphysical speculation that had no bearing in observation or the reduction of language to the physical world in the way of concrete objects and operational definition. 'Theory of Everything'. If you take ToE to be the typical physical understanding, then what's best to say is that it is quite possible that we may integrate quantum mechanics and relativity, supplant the standard particle model.

Alternatively, if you approach it from a sociological angle, perhaps as a scientific constructivist, a theory of everything might encompass not only a unified model of the fundamental forces (gravity HAS to be quantified! ; ) but also the develop of the philosophy of science itself with 100 more years of research. In such a view, the theory would be a social edifice of language that facilitates practice, and can't be reduced to anything less than the observations of all people everywhere. Maybe something like Asimov had in mind in his foundation trilogy with psychohistory.

But, if you're thinking there's going to be a limited set of axioms that generate all solutions and predictions and completely explains everything in the universe, then that's an entirely different perspective on theory of everything. Then giving all of the theorems about epistemological incompleteness and non-determinism, it doesn't seem likely.

In any case, you are now a fully initiated member of this site when you get the boilerplate response: "depends on what you mean by the 'theory of everything'". Once you build up the vocabulary in the domain of discourse, you'll know because you'll be able read Wilfrid Sellars, John McDowell, Ian Hacking, Bastiaan van Fraassen, and other's and not be entirely lost.

Good luck!

Answer 2

No, the incomputability of Kolmogorov complexity merely means that we probably won't know for sure if we have the right TOE. We may indeed one day have a theory that explains the whole universe in a simple and satisfactory way. We'll just (probably) never be able to prove that this is the simplest possible theory; there might be a simpler one that we just haven't found yet.

Also, Kolmogorov complexity is not computable but it is limit-computable. That means that given enough computation time, we can eventually settle on the correct Kolmogorov complexity for any piece of data. "Enough computation time" could be 10^5000 years or something like that, or even much worse, but eventually we'll get there. Finding the minimum Kolmogorov complexity (in the limit) is a simple process. All you have to do is simulate all possible programs in "parallel" (dovetailing the computations). At any given point in your parallel calculation, you will have a "shortest program so far that terminated and matched the observations" (abbreviate SPTMO). The length of the SPTMO will decrease as you keep calculating, eventually settling on the Kolmogorov complexity of the observations.

Incomputability of Kolmogorov complexity just means that even once the process settles on the shortest SPTMO, it's not always possible to prove that it has settled, i.e. prove that a better SPTMO will never be found. (Except, sometimes, for short enough SPTMOs, it is possible to prove that it has settled; that depends on the observations.)