Tim’s post just reminded me to write something on Gregory Chaitin. I’ve been writing about this area a fair bit in my thesis, in light of his relationship to Wolfram’s research. Often enough, if you highlight differences between two thinkers in one specific field, you can transport or unpack those differences in a completely different field. And the impact of computer science needs to have a greater efficacy in media theory and art production than it does at present.
Now in my eyes, Chaitin is less a mathematician or a programmer or a scientist, but a philosopher who happens to do mathematics, programming and science. How many philosophers would write and publish a book with a bundled copy of their proof coded in LISP? (see the Limits of Mathematics) (LISP is a procedural computer language for mathematicians). I would also say the same for Wolfram, but Wolfram probably thinks of himself as unlike anyone else that has ever come before and anyways, he is far more of a rationalist than Chaitin. Chaitin is fully on the side of contingency, Wolfram is on the Leibniz – rationalist side (but I don’t adhere to that side of Wolfram personally as we will see).
The reason Chaitin is a philosopher, is that he aims for a type of metaphysical commitment one rarely sees in the field of pure math. Thats the biggest reason why mathematicians have never liked what he is doing and why his work is controversial; because he exposes something that can never fit into the long term projects of the field. A field which fully believes that mathematical theorems of reason are achievable by finding the stable axioms and deducible theorems.
The easiest way to explain Chaitin’s result is to explain what Godel and Turing did before him. Godel completely destroyed Hilbert’s problem (or the 2nd problem) by showing that you can use Formal Axiomatic Systems and Godel Numbering of the Primes to encode a paradoxical statement which undermines the completeness and consistency desired by those systems within the systems themselves.
Alan Turing, kind of made it worse, not by making the math anymore paradoxical, but by first showing that you can convert objective Formal Axiomatic systems of logic into equivalent computational statements, the mechanical programs of which produce decidable or undecidable outputs, based on recursion and programmable procedure. You can then use these theoretical computers to then show how there can never be any general purpose algorithm which will tell you whether a given program will halt or not (Kleene later defined it as halting, not Turing). This was Turing’s proof reductio ad absurdum, because if there was such an algorithm (a totalizable algorithm, similar to the impossibility of non-totalizable sets), you could then check all programs in size order and check if they obey the rules of system. Checking whether a program halts or not is the easiest thing ever; you just need the patience in waiting for it to halt or you choose to give up. But a more general algorithm that computes this for you cannot exist.
So as well as discovering computation, Turing also discovered the fundamental limit of computation at the same time. And Turing made it worse, by transforming this metamathematical paradox into a type of physical law within objective mechanical procedure. We all know what happened to the status of the computer after that.
Well Chatin (as I understand it) makes this even worse. His two incompleteness theorems go into this area in more depth. He transports the situation again, but this time into randomness and probability theory.
The basic theorem is this; instead of looking at one program, put all possible programs in a box and blindly pick out a program. What is the probability that this program will halt? One can express this probability as a real definable number but Chaitin chooses to express this number in an infinite binary, base-2 arithmetic expansion native to information theory and relative to Borel’s paradox (an infinite number between ’0′s and ’1′, where each independent ‘bit’ is an independent fair toss of coin at each stage: either 1 or 0).
So whatever this real number is, it has a definite value, just like π or the number ’45298′, and it is in binary notation, so the number must be greater than ’0′ and less than ’1′. It is defined as Chatin’s Constant and because there are infinitely many possibilities, Chaitin just uses the notation Ω.
Ω can be defined as an infinite sum, and each N-bit that halts contributes precisely 1/2N to the sum. Basically each N-bit program which halts adds a 1 to the Nth bit in the binary expansion of Ω. Add all the bits for all programs that will halt, and you will get the specific precise number of Ω. This makes it sound as if it were a real number which is computable, but it isn’t. Ω is perfectly well defined and it is a specific number, but it is impossible to compute in its entirety. In fact, Chaitin’s proof shows that Ω is irreducible, maximally unknowable and cannot be defined by any finite mathematical theory no matter what the computer language. The output cannot be condensed into a finite number, which is simpler than it is. The point being that the first N digits of Ω cannot be computed using a program shorter than N bits – that’s the irreducible part.
In information terms, it is structurally random, with little to no structure, and no rational way of reasonably reducing it to something shorter than it is. Mathematics therefore is, at base, irreducibly complex and random according to Chaitin. Ω is place where mathematics has no structure and no reducible reason – in short rational numbers are true for no reason. As Brassier argued (and used it to critique Badiou’s subject) it’s almost like an incoherent noise with no structure to it all and from where a narrow rational layer of normal rational mathematics can be found.
I favour Wolfram’s undecidable approach, which doesn’t get caught up in probability theory, but at a price, for one must adhere to deterministic pesudo-complexity, albeit a pseudo-complexitiy which is more pragmatic. Unlike Chaitin, Wolfram thinks that there is one fundamental program to explain all complexity, which I don’t follow at all, for the reason that Turing discovered. However that does mean we have an either/or situation, with rational truth on one side and irreducible complexity on the other. One can simple state the OOO wager (and this would be my wager) that the recursive execution of rules from axiomatic systems are irreducible in themselves, with no undermining or overmining. And this, somewhat unexpectedly, is where creative art has something important to add.
5 Comments
Hi Robert,
Very interesting post. It looks we are working on very similar things.
Actually, Chaitin thinks he is the true Leibnizian. He pushes this view strongly in his key philosophical work Meta Math!. The least one can say is that this would be a Leibniz not in conformity with the traditional picture . But to decide the issue would require working through all the writings of Leibniz. It is notoriously difficult to say what Leibniz is actually saying as a whole given that what he produced is in so many occasional pieces, letters, etc. . David Lewis simply threw his hands up and does not refer to Leibniz once in his work (he says cannot tell if Leibniz said everything he does already or not). But reading through Leibniz is something I am very slowly trying to do. Hopefully I will be able to clarify one day who is the true Leibnizian if that is possible.
What I call the Name of God per the manuscript I referred you to (it should be available online soon–maybe in January) and what Woflram means by the ultimate cellular automa would itself be an Omega bit-string. But necessarily finite. While the book I referred highlights Woflram, what I am working on now is more so focused on Chaitin and showing how the Name of God exists using his theory.
I am working on a manuscript on these issues I hope to finish soon. In it, one of the key points I make it in it is that the universe cannot be described by an infinite omega is that all the regularity of patterns shows that there is too much reducibility/compression for what we observe to be defined by an infinite omega bit-string.
I wish us both good luck on our respective projects.
Noah
Hey Noah,
We are working on very similar things – but I would say that my ‘prism’ so-to-speak, upon which everything is viewed is in reference to the autonomy of computational art specifically and ‘art’ more generally. Clearly theology, ontology, mathematics and media theory are heavily involved, but the necessity of art comes first for me. I think both of us (more so me
could learn a lot from each other on our respective projects.
It is notoriously difficult to map a system to Leibniz’s corpus, he’s the archetypical OCD philosopher. Chaitin is actually very good at locating the first remnants of AIT from Leibniz’s Discourse on Metaphysics and reading it through rational, simple scientific reason both in mathematics and physics.
If I’m honest I’m still left scratching my head on how you might show the name of God in Chatin’s AIT or Wolfram’s own ‘Theory of Everything’ – I’ll understand a bit more when your ms is released, but is it in any way related to the notion that Chaitin puts forward in his own digital physics – the notion of God being a programmer? I’m probably way of the mark here.
best wishes
Hi Robert,
First let me clarify a point. I said earlier that what I am calling the Name of God is a finite omega bit-string. What I meant (and this is why I don’t like to post to blogs because I prefer my missteps to be buried in drafts of manuscripts) is that the Name of God is both irreducibly complex in Chaitin’s sense and a finite bit-string. Technically, an omega is an non-computable real number so by definition it is as infinite as any real number (the one Chaitin likes best is that which expresses the probability of the Turing halting problem). What I am saying is that the ultimate bit string (Name of God for me –for Wolfram the automaton expressing the universe) would involve both irreducible complexity (non-compressible) but also involve infinity (like pi or e do as real numbers rather than omega). As I said before, I do not think the universe as such can be described by omega given the amount of regularity and order (that is, compression) found in it. I think omega still plays a role in theology and is related to the name of God and other issues but not in the sense of being how the universe is. If omega describes the universe, then Meillassoux is right. These things are still a little in flux with me. But at some point over the next month or so I hope pin it down in a first (and hopefully consistent) expression (without too many missteps).
As for God as programmer, there is an element of that. But I am not pushing a model where God is conceived as a positive entity in the world. God’s programming for me takes place through God’s withdrawal and self-contraction.
For Chaitin on Leibniz I really recommend the youtube lectures if you have not already watched them (the ones at Lisbon, Carnegie Mellon, etc.). All those lectures are great in any event. Chaitin makes some really good points about how with Leibniz he would just dash off 5 pages in a letter or small piece and come up with a good idea. This is why it’s difficult to say what Leibniz said. He would express an idea and drop it. I think this aspect of Leibniz means if one is going to write a book on Leibniz it is most fruitful not to write it in the traditional way (that is, just trying to note what he says in each place and what it means).
You are right. I am not looking at art in any real way. I am actually looking more so at evolution/biology. This is another way Chaitin is important (although we are at odds on how to interpret what his attempts at merging computation and biology show).
We are also different in that I think OOO is essentially a dead-end and misguided approach. Objects cannot be sets of irreducible complex bit strings in the OOO sense. I do not think OOO can even admit the notion of the bit. OOO is transposing Husserlian intentional objects onto being itself in act of reification (with the caveat that they ‘withdraw’–which just means their unity is not perceivable and only intended ultimately– and perceive each other–although there is no phenomenological analysis of the analogy from human perception that could flesh out such a claim in the way Husserl gives such an analysis in Cartesian Meditations relative to subjectivity). If an OOO object were a set of non-compressible bits, then the object itself would be the computation of those bits. That means one has a formula that captures the object itself as such. The conception of the thing and the thing would be the same. It’s then just a matter a la Woflram to see how that computation plays out. The bit I argue involves the existence of the void, numbers, pure differentiality, etc. Admitting that things are bit strings means admitting that at bottom there is an ‘atom’ and that atom is relationality in itself. It’s not surprising that OOO has nothing to my knowledge to say about numbers as objects or the nothing/void as non-object. These are things in the book already coming out.
But now I have truly said too much. Time to bury back down into my mole hole and dig.
Best,
Noah
Thought it would best to elevate this discussion to an actual post of its own HERE, where i’ve spelt out the reason why I disagree.
Not that I like disagreeing, but you know its the ‘academic thing to do’.
Readers of this blog may be interested in my book “Proving Darwin: Making Biology Mathematical” published by Pantheon in New York in May 2012.
Best wishes,
Gregory Chaitin
One Trackback/Pingback
[...] important conversation, so its worth elevating to its own post as it were. His original comment is here, but I’ve directly copied what Horwitz thinks regarding OOO and computation. We are also [...]
Post a Comment