On Sat, Aug 17, 2019 at 5:17 AM Bruno Marchal <[email protected]> wrote:
> > On 16 Aug 2019, at 19:06, Jason Resch <[email protected]> wrote: > > Would Chaitin's constant also qualify as a compact description of the > universal dovetailing (though being a single real number, rather than a set > of rational complex points)? > > > It does not. In fact Chaitin’s set (or “real number”) is not creative > (Turing universal) but “simple", in that Post sense given above. You can’t > compute anything with Chaitin’s number. It is like a box which contains all > the gold of the universe, but there is no keys to open that box. > > But “Post's number” , which decimals says if the nth program, in an > enumeration of programs without inputs, stop or not, is creative, and > “equivalent” with a UD* (seen properly in the right structure). But the > term ”compact” does not really apply here, unless perhaps you write the > digits in smaller and smaller font so that you can write it all on one page. > > You can look at Chaitin’s number as a maximal compression of Post’s > number. Post number is deep, in Bennett sense, where Chaitin numbers is > shallow and ultra-random. Chaitin’s number is the Post’s number with all > the redundancies removed. You cannot do anything with it, except gives a > non constructive proof of Gödel’s incompleteness (which was already in Emil > Post, but without that “probability” interpretation of “simplicity”. > If Chatin's number is a maximally compressed Post's number, what makes one creative and the other simple, or one a representation of dovetailing and the other not? Both require infinite computing resources dovetailing on all computations in order to generate them (don't they?). I think I am missing something here. > > An interesting paper, that Brent points to me some years ago, which shows > this and more is the paper by Calude and Hay: "Every Computably Enumerable > Random Real Is Provably Computably Enumerable Random" (arXiv:0808.2220v5). > Here: https://arxiv.org/abs/0808.2220 > >From the abstract: "We also prove two negative results: a) there exists a universal machine whose universality cannot be proved in PA" This is surprising to me. I thought it was generally easy to prove something is Turing universal, simply by programming it to match some other universal machine. I will have to read it to see how. > > That paper is also useful to see that PA can prove the existence of > universal numbers, computations, … (without assuming anything in physics, > which could help some people here). But it is a bit technical. It also > assume that ZF is arithmetically sound, which I believe, but is not that > obvious, especially with Mechanism! > > Both Chaitin and Post numbers contains all the secrets (of the universal > dovetailing), but Chaitin’s number, by removing all the redundancies, is > unreadable, and just as good as total randomness or mess. Post’s numbers on > the contrary is comprehensible by all universal machines, so to speak. > Put in another way: with Post numbers, there is full hope for a decent > measure on the relative computational histories. With Chaitin’s number, > there is no measure at all, like if all computational histories were > unique, somehow. > I view Chatin's number as Post's number compressed so greatly you need to run a Busy_beaver(N) number of steps to decompress N bits. Is this accurate? > > This does not mean that Chaitin’s number is not interesting for Mechanism. > I think it will play some role in the thermodynamic of the computationalist > physical reality, but not in its origin (which Post’s number does). > > Could you clarify the meaning of the thermodynamics of computationalist physical reality? Is it equating physical randomness with the limit of the infinite complexity of the dovetailing computations? Jason -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CA%2BBCJUioBg%3DNTAJ7yTYcOj65dBgYz4mKTh7iwu9mJznGW-E1bA%40mail.gmail.com.
