Essay Abstract

Many people believe that the universe is a giant computer. This view implies that what is uncomputable has no causal power. We propose that, to the contrary, at least one uncomputable object, Kolmogorov Complexity, does play a causal role in the physical world, and that we have good scientific reasons to therefore believe it exists. We use a simple set of arguments, based on the probabilistic extension of algorithmic information theory, to show that such a causal role is not only consistent with the best evidence from cosmology, but also predicts an otherwise mysterious feature of our environment: mutual explainability. Mutual explainability is the fact that things that tend to correlate with each other also tend to explain each other.

Author Bio

Simon DeDeo is external faculty at the Santa Fe Institute, and assistant professor in the Department of Social and Decision Sciences at Carnegie Mellon University, where he runs the Laboratory for Social Minds. http://santafe.edu/~simon

Download Essay PDF File

Dear Prof Simon DeDeo,

Thank you for giving us a wonderful essay on what computers can't do ( Uncomputability). The KC is complex program, and it is even not came in a full program form till now. Is this Artificial intelligence in some other words? They say full AI is also very complex....

Hope you will get some spare time to have look at my essay " A properly deciding, Computing and Predicting new theory's Philosophy" also, and give your valuable comments....

Best regards

=snp

    Hello SNP --

    Thank you. I think getting these questions right is crucial for GAI, so I'm glad you asked. I'm currently in the middle of Reza Negarestani's book Intelligence and Spirit, which you might like if you find this style sympathetic.

    Some great essays this year, looking forward to reading yours.

    Simon

    Dear Simon,

    What is that book "Reza Negarestani's book Intelligence and Spirit" and tell a few words about it and how to get it?

    By the way what is GAI? And please clarify my question about AI, and when you can spare some time visit my essay ....

    Best

    =snp

    Dear Simon,

    this is an exceptionally well written, and more importantly, well argued essay that brings a novel, and intriguing, perspective to the question of whether non-computable objects matter in the world.

    It's an interesting perspective to try to accord an abstract quantity causal significance. On the face of it, it seems to invite some strange notions---if I say, 'the real number line contains more elements than the set of natural numbers', has 'the real number line' with its uncountably many elements caused me to say that, and if so, do we need to say that it exists, in some way? What about 'the round square copula on Berkeley college, which is pink'? This invites the issue referred to by Quine as 'Plato's beard'---and dealt with by his dictum 'to be is to be the value of a bound variable', so that the offending object can be freed from any causal relevance---'there is something, such that it is round, square, pink, and the cupola of Berkeley college' does not need for there to be such an object, in order for me to utter this sentence. Hence, it's not that what's caused me to utter the phrase.

    But of course, you follow a different approach. Abstract objects, in your case, exist because they have causal consequences regarding what happens in the world, not merely what is being referred to. One can't assert the reality of Pegasus just by referring to it, but if Bellerophon is carried away by a winged horse, it would be hard to deny its existence. So you say, odd numbers make it hard to split a check; electric fields move particles around. Hence, these things exist.

    I'm of two minds regarding this argument. First of all, it seems to me that there can be, strictly speaking, inconsistent mathematical theories that nevertheless successfully describe physical situations---quantum field theory and general relativity are mutually inconsistent, yet can be brought together to predict, say, black hole evaporation. Certainly, we expect for there to be a further theory such that it is consistent, and reduces to the others in the appropriate limits, keeping its predictive successes, so that one can say, well, the objects of that theory exist, instead; but it at least urges caution with respect to this sort of argument.

    However, I don't think that your argument is suspect, in this sense. (It's also a thing of beauty, I have to say.) Essentially, you appeal to the fact that the algorithmic mutual information, in the average, approaches the Shannon mutual information only if the initial probability distribution is of low KC---and thus, if we find that whenever things are correlated (mutual information measures correlation), they are also co-explainable, we obtain evidence for the smallness of the initial probability distribution's KC. In this sense, Kolmogorov complexity has a hand in the makeup of our world; no being with access only to computational resources could have set things up this way. If god exists, she must have access to an oracle.

    As I said, I think this is a highly ingenious argument. But isn't it vulnerable to anthropic counterarguments? It's easy, given sufficient resources, to simply compute all universes. Then, there will be some with low initial Kolmogorov complexity; only in those will there be beings that have had any luck at explaining their world, and thus, that could hold some sort of conversation like the one we're having here. But if the world were like that, the conclusion that KC plays some fundamental role would be misguided---the appearance would be an accident of placement, so to speak.

    Anyway, I'm running out of time, and I haven't even gotten to the part I liked the most---namely, your notion of different explanatory reference frames. If I read you correctly, one way to frame this is that different explanations make sense to different people, because, essentially, while both explanations may be correct, one could take an unfeasibly long time to unpack for person A, with the issue reversed for person B---so even though both, within limits, are saying something true (although one explanation might be the more simple one, we couldn't really show this to be the case), they might be mutually almost unintelligible.

    I think this is a highly intriguing thought, and deserves to be developed further. So, I wish you the best of luck in this contest, thanks for submitting your essay, I will spend some more time thinking about the issues it proposes!

    Cheers

    Jochen

      Hello Jochen --

      Thank you for your gracious comments here. I'm drawing that notion of cause in part from the scientific naturalism of Ladyman et al ("Every Thing Must Go"), who say that our ontologies should be those of the best scientific explanations. But I doubt they'd agree with me after that! I do think it's possible to be a scientific naturalist at the same time as rejecting computational naturalism (the computerland) though.

      One thing I might say to your remarks on GR vs QFT is that the account here explains exactly why that inconsistency bothers us so much. Even if it were possible to describe everything we wanted to by a patchwork of inconsistent theories, I think we'd feel sad if we stopped. We want to know "what's" there. We attribute a reality to the objects we consider to have causal power.

      Your question on whether an anthropic argument can get us explainability on its own bothered me a lot as I was putting this together. Explainations do matter to our survival.

      In response, I'd say that explanations come pretty late in evolution. A bacteria does not explain its environment. It leverages correlations between different parts of it--concentrations of this ion correlate with a stiffening of the membrane, etc. You can always have correlations, even if they can't be explained--a high KC universe is not less "predictable" in the sense of having lower mutual information.

      It is of course hard to describe an environment with low mutual explainability but high correlations, simply because (of course) in order for me to describe that environment to you, I have to use a lot of words. (I gesture at it with the Robert Anton Wilson remark.) So I'm not entirely sure if correlations without mutual explainability are enough to get life up and running.

      But here's one example where they are. Imagine we have a fine tuned universe (high KC) where everything was set up to roll forward *exactly* like this one, until tomorrow afternoon, when everything stops making sense (hidden correlations cause unicorns to materialize out of asphalt, etc). You can call these the grue Universes (grueniverses). Mutual explainability breaks down, and everything that comes next is explainable only in terms of the initial conditions.

      If Universes are generated without a KC preference, I think you can prove that these grueniverses are actually much more common than the normal one--and so (among other things) it's very unlikely that we just got lucky to have one whose grueniversal properties stayed hidden for so long.

      I'm very pleased that someone who likes Quine also got something out of this essay.

      Yours, and best wishes from Pittsburgh,

      Simon

      Dear Simon,

      regarding this:

      I do think it's possible to be a scientific naturalist at the same time as rejecting computational naturalism (the computerland) though.

      I have to say I emphatically agree. I think computationalism is a very attractive idea---in part, because the 'linkage' of concrete physical entities with abstract objects, like computations, seems to hold a certain promise for explaining the connection between the brain and the mind---but unfortunately, I don't think it holds up, in the end. In fact, I recently argued that any relation purporting to give an account of implementing computation can't itself be computational (and argued for some---I think!---interesting conclusions of that regarding the mind).

      So I don't really have a problem with a reality that isn't computational---and in fact, I've used the non-computability of Kolmogorov complexity myself to try and give an account of quantum phenomena (and investigation continued in this year's essay).

      But enough with the shameless self-promotion! Back to your fine essay.

      I like your notion of the 'grueniverse' (and of course, the reference to the problem of induction is very appropriate, as that's exactly what we're trying to do---and indeed, the formalization of induction by Solomonoff does make use of algorithmic information theory). Certainly, such a universe would explain our getting to right here, right now just as well as one with low initial KC.

      But I'm not sure if it helps your argument: at any given point, provided that the grueniverses outnumber the universes (let's not worry about measures and the like just yet), we should, from our observations up to this point, rather be more justified in inferring that we live in a grueniverse, than that we live in a universe with low KC (or sampled from a low KC probability distribution). So at any given point, we'd be faced with two hypotheses---1) mutual explainability holds because we live in a low-KC universe, and 2) mutual explainability holds because we live in a grueniverse. In the case of 1), your argumentation would suggest the 'reality' of KC, but are we, given observations of any length, really justified in concluding 1)?

      So, while it might be unlikely that grueniversal properties take a long time to reveal themselves, given no preference of KC in universe creation, that wouldn't really license us to more than to constantly being surprised that things continue being apparently explainable.

      I also wonder how your notions jibe (if they do) with Schmidhuber's 'Algorithmic Theories of Everything'; he starts off with the assumption that the probability distribution from which our universe is drawn is formally describable, and goes on to show that it's then biased towards universes with a short description---hence, the observation that we live in such a universe seems to yield the contrary conclusion than your argument does.

      I'm still struck by your elaboration on the distinction between correlation and mutual explainability, I have to say. It's the sort of subtle thing that almost seems obvious once it's pointed out---obviously right, not obvious to discover---and I think it's got the potential to clarify a lot of muddled notions (some of which might be my own).

      Cheers

      Jochen

      So I think the grueniverse does actually work in this case. First we condition on the Universes being "safe enough for intelligent life" that we get to the world historical moment of us having this discussion right now. The concern is that these have to have mutual explainability--let's take that as given.

      We have two hypotheses: KC (the argument of this paper), and CN (computational naturalism, random generation w/o use of Kolmogorov Complexity). By assumption, right now, our experiences are such that:

      P( E | KC) = P( E | CN ) = 1 (or so)

      Now wait ten minutes and get experiences E2. Sadly, no unicorns emerge inexplicably from the asphalt.

      P( E2 | KC ) = 1

      P( E2 | CN ) = epsilon

      Argh!--for some reason my remarks got cut off. Let me complete the argument. Epsilon gets very small very quickly, because grueniverses are dense in the set of universes. Then we have

      P(CN | E2) is proportional to epsilon x P(CN)

      while

      P(KC | E2) is proportional to P(KC)

      So even if you think this idea is crazy, you only need to wait a little while to accumulate high confidence relative to computational naturalism.

      Thank you very much for engaging with the essay--this is very helpful for me, and I hope to put these ideas in a later version. Meanwhile, thank you for pointing me to your own work. I'm jumping back in this evening and look forward to engaging.

      Yours,

      Simon

      Dear Simon,

      yes, I think your logic is sound there. There's a question, I suppose, whether the grueniverse-continuation really corresponds to something that we'd consider as us having any sort of experience at all---probably the vast majority of such universes wouldn't correspond to anything as nice as getting a free ride on a unicorn, but to something much wilder than that, and one might want to question whether they would be present in some anthropically selected subset. But intuitively, I'd say that the 'slightly weird' universes still ought to outnumber the 'explainable' ones by some large margin---although on the other hand, now that I think of it, I'm not sure we're not actually living in a 'slightly weird' universe!

      These are, however, details. There's another point I found highly interesting about your article, which is the existence of 'explanatory reference frames', in some sense. In a way, we come loaded with some heuristics, and perhaps some explicit methods, of compressing information that we come into contact with; differences in this 'basic mindware' then account for different explanations making sense to people with different backgrounds (stretching terms here somewhat). So there might be things that I can make sense of, or that make sense to me, perhaps, but that seem utterly random to somebody else. That seems a rather dispiriting conclusion (and I'm not sure if it's one you draw, or if it's one more reason to reject computerland).

      But I'm reminded of another notion of Schmidhuber---the idea that we're driven by compression progress: i. e. that we're not limited to a single compression algorithm, but can pick up novel ways to compress information, basically from the environment. This is something, I think, a little different from merely being presented with a new compression algorithm to learn---you'd just iterate the problem: for that new 'way of explaining' to make sense to you, you must already be able to explain it, in some sense.

      But perhaps we can point to what we can't say directly. (Although, I suppose, in computerland, everything can be said, in principle.) So Schmidhuber suggests that we can adapt novel ways of compressing stuff, essentially via art---it's not so hard to see that lots of art is, in one way or another, concerned with compression of some kind (lots of it, of course, also isn't): rhymes and meter are ways of introducing redundancy into text, limiting the possibilities of words that follow; symmetries likewise are powerful tools of compression; and so on.

      I think that that's ultimately a bridge too far, but I like the general thought---even if the insistence on formalization makes it come out a little bland: perhaps through art we can communicate some things we can't via explicit explanation. I'm not sure it's right, but I think it's a nice thought.

      Anyway, that got a little more into free association than I originally intended. I think I best leave it at that, for now.

      Cheers

      Jochen

      Dear Simon,

      Great piece, I am glad you mentioned it in my own entry, as I had some time to read essays today and came soon to yours. Let see what it does to my primacy effect (I'll love to know what my own article does with your effect also). And, indeed, there are nice similarities in our opening sentences.

      Your description for a possible KC-universe generating scenario is intriguing and reminds me of something similar I heard about some time ago. I can't recall the source, but it was about universes being created as consequences of other universes and there was some kind of evolutive pressure on the process. I need to hunt that one down.

      Anyway, I must say I have a problem with the suggestion that simplicity might be a good way to pick correct theories. You do not say that explicitly but you do suggest that as an argument. I do like simplicity and I think it does have a role in science. But, unlike other physicists, I think the role simplicity (and, with that, measures of complexity) does play is based on human limitations. Simple, assuming human language and knowledge, is easier to use and that makes it preferable. But that is not the same as claims of truth - which should not be made - or even probabilistic truth.

      Best,

      André

        Hey André! I think you're thinking about Lee Smolin's proposals regarding black holes forming baby universes--rather clever, though focused on the capacity of universes to create baby universes, rather than to be efficiently explainable.

        "Simplicity" is a powerful concept, and the question is why it works. There are IMO two answers:

        1. it works because the world is explainable--it turns out things do have simple descriptions, so let's prefer those.

        2. it serves as a regularization term, or a block against overfitting. Certainly this is why something like LASSO or sparsity constraints work in machine learning. It's a bit of #1, but includes the fact that we also have noise, and noise is uncompressible, so you can penalize things that model noise by penalizing complex things.

        Physicists do also like a #3: simple things are easy to communicate! These come from cognitive constraints. But we certainly wouldn't say "X is likely to be correct because I can understand it" (we might say "X is likely to be correct because it's simple, and by virtue of that second fact, it happens that I can understand it").

        Yours,

        Simon

        Yes, it was Smolin's idea. Much easier to track now, thanks.

        I am not saying simplicity does not work, it did in the past, and it will probably work well in the future also. But there is a clear bias we introduce in explanations as we do start looking at the simpler ones. Assuming there are several equally good explanations (probabilistic underdeterminancy), we would find the simpler ones first, just because we are looking there first. That does fit nicely with your #3.

        The world is explainable might mean different things, as you know. It might even be just partially correct, in that we can get part of the answer but not the complete version, in principle. And yes, avoidance of overfitting is important. In principle, Bayesian methods do penalize more complicated models, so you would not need that. But, even in simple cases of model comparison, you crash into problems with the priors.

        In any case, I think it is essential not to assume more than we actually can say from observation. Introducing new theories is fundamental, even metaphysical ones, but we must withdraw judgment far more often than it is done in the physics community.

        Yours,

        André

        Dear Prof. DeDeo,

        thank you for a nicely written essay, very accessible and with a lot of food for tought. I enjoyed very much reading it. I found particulerly appealing your section 4, where the main thrust comes. I believe there is some element of convergence between our views, for instance when you say that "a mathematical object exists if it plays a causal role in the natural world". In my essay you will find an argument based, if not on simplicity, on some principles that tries of finiteness (of the Kolmogorov complexity, in fact) that tries to disentangle the mathematical abstraction with the physical meanings. I would appreciate your opinion on that.

        Best wishes and good luck for the contest!

        Flavio

          Lovely, Flavio. Looking forward to reading it. It's worth thinking about how to flesh out that rather off the cuff remark about causality...

          Dear Simon,

          I liked very much your essay, both how it's written, the connections it makes, and particularly the idea to refute the physical Church-Turing Thesis by showing that Kolmogorov complexity plays a causal role in the universe through the mutual explainability.

          It's relieving to know that the chances we're not in a simulation went down :) OK, I'm not really worried about the possibility that the world is a simulation. The reason for this is expressed better than I can do by Sam Harris: "whether or not you're already in the Matrix or in a dream or in some other way distant from the base layer of reality, the fact that it's like something to be you is the fact of consciousness, and it's the one thing that can never be in doubt." This works I think whether or not consciousness is reducible to computation. If it's reducible, then a consciousness in a simulation is as good as one in a real world. If it's irreducible, then even if it is plugged into a simulation like a role playing character or like in the Matrix, the argument from Sam's quote shows that there's something real about it.

          Cheers,

          Cristi

          4 days later

          Hi Simon!

          Fantastic essay! I love how you talk about KC in your examples.

          I was wondering if you could talk a bit more about this: "The idea that mutual explainability provides evidence against the physical Church-Turing Thesis is radical." I think this is generally true and also extremely interesting. But I'm also wondering how much that depends on a and b are encoded. For A, there are several different ways to realize it, and on top of that, far more ways to encode its realization into a state. Have you considered this distinction before? For example, a person who is deaf would encode states of the world completely differently than a person who is blind. I'm wondering if this encoding has an impact on the compatibility of a problem or the physical realization of an object. Maybe there is no such encoding that a and b have mutual explainability, or perhaps a explains b only when encoded in a particular way.

          I'd be really curious to know what you'd think! I also talk about this idea in my own essay, I probably do a much better job explaining it there.

          Cheers!

          Alyssa

          5 days later

          Dear Simon,

          Thanks for your essay.

          I have now come to the dreadful realisation that, in my essay, I have created a computerland world with the future predicted by a simple algorithm that has to be run over and over again, possibly a billion or more number of times, to predict how a certain set up will develop after a certain time t.

          In that world there is just one algorithm that continually loops: it returns results, then acts again on those results and so on, until time t is reached.

          But then it occurred to me that perhaps (just perhaps) I can measure the Kolmogorov Complexity of that algorithm. What if I defined complexity as the inverse of the number of times that the algorithm had to completely loop to get to time t (on the basis that the simpler a program, the more loops it will have to make to achieve a result)? Indeed, the algorithm could be adjusted so that it could also tell me how many loops it had performed, thereby telling me its own complexity without the need for a different KC program. I could also compare my algorithm with other algorithms that predicted the future using the same sort of looping process and then be able to say which was the simplest by comparing the number of loops to get to time t. What then? Would that mean this type of KC is actually computable?

          What do you think?

          All the best. I really enjoyed your essay and learned a lot from it.

          David

          12 days later

          Dear Simon,

          Thank you for your interesting and engaging essay.

          I appreciated your discussion on KC, and I was pleased to find that your essay got me thinking about a good many things.

          Your focus on self-reference and KC made me think more deeply about consciousness. I studied neuroscience during posdtdoctoral years in the mid-1990s. At that time, the field referred to consciousness as "The C Word", and serious discussion was somewhat taboo.

          The topic interested me, and my thinking about the research performed by colleagues led me to believe that consciousness was more or less an illusion that arose from the brain modeling and describing itself. It wasn't until, I read your essay that I was forced to think about this idea of something modeling or describing itself as a form of self-reference.

          - Do you have any thoughts on this perspective?

          - Could this self-reference by one of the reasons why we intuitively feel that consciousness is so magical??

          - And what are the prospects for an AI that models itself?

          I was struck by the point that you made stating that a computer simulation can only use computable numbers. If we were in a computer simulation, there would be many holes. Would these be detectable?

          Are these hidden because the rationals are dense?

          Or would they be unnoticeable precisely because we too are simulations?

          Thank you for the thought-provoking essay!

          Kevin

          Near the end you touch on something I myself have come back to many times: the universe admits of explanation. That means the universe is structured in such a way that a (small) subset of itself can construct a compression of the whole. You cite a counter-example of Robert Wilson. Another, which I have often thought about, is Jung and Pauli's synchronicity. We can imagine correlations between events in different causal chains, and even spacelike separated events (beyond EPR) that would demand a very different mode of 'explanation'. How can we explore the possible existence of patterns of events scattered over the spacetime manifold that are not captured by standard Lagrangian dynamical evolution?