On Sat, Aug 17, 2019 at 5:17 AM Bruno Marchal <marc...@ulb.ac.be> wrote:
> > On 16 Aug 2019, at 19:06, Jason Resch <jasonre...@gmail.com> 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 everything-list+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CA%2BBCJUioBg%3DNTAJ7yTYcOj65dBgYz4mKTh7iwu9mJznGW-E1bA%40mail.gmail.com.
