> On 24 Aug 2019, at 00:23, Jason Resch <jasonre...@gmail.com> wrote: > > > > On Sat, Aug 17, 2019 at 5:17 AM Bruno Marchal <marc...@ulb.ac.be > <mailto:marc...@ulb.ac.be>> wrote: > >> On 16 Aug 2019, at 19:06, Jason Resch <jasonre...@gmail.com >> <mailto: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.
Chaitin’s number is the result of the computation, which consists in compressing the Post’s number, and making it totally unreadable. The result of a computation is not equivalent with the computation leading to that result. (That’s why the Adam machine which compute a very long time to get the answer 42 is funny :). It can be shown that such computations exist. Some predicate can be arbitrarily hard, despite they will answer 0, or 1. That can be proved by diagonalistation. > > > 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 <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. Even if this method works for some big, but finite sample of numbers, that would not be equivalent to proving that the machine does its work. By Rice theorem, we have something more general. The set of number x such that phi_x computes the factorial function (say) is not computable. We cannot test if a program compute factorial or not. You can guess that such a program would solve all halting problems. Imagine the program search for a proof in ZF of the Riemann hypothesis, and if you find it output the usual factorial (n). If you decide algorithmically if that code computes the factorial function, you would be able to solve mechanically if Riemann hypothesis is true. But you can also prove Rice theorem directly, using the second recursion theorem. If you can decide if a program compute some given function, you could use them to build a recursive permutation without fixed point, which cannot exist by the recursion theorem. Most attributes of programs are non computable. > > > 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? I think so. Chaitin numbers encodes not more than the Halting oracle, in a maximally compressed way. > > > 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? That seems more like the arithmetical explanation of the quantum indeterminacy. The thermodynamics would be more related to some identification of the length of a finite computation and its code. A short code leading to a long computation would contain more energy than a short code leading to a short computation, up to some constant. But the length of the computation is not enough, and it is better to use the depth of it (following Bennett). The UD would have infinite “energy", like arithmetic, but the program “10 GOTO 10” despite leading to an infinite computation has basically no energy at all. Bruno > > 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 > <mailto: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 > > <https://groups.google.com/d/msgid/everything-list/CA%2BBCJUioBg%3DNTAJ7yTYcOj65dBgYz4mKTh7iwu9mJznGW-E1bA%40mail.gmail.com?utm_medium=email&utm_source=footer>. -- 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/16B91C8F-4026-42E9-BF79-3391B3454017%40ulb.ac.be.
