> On 11 Mar 2021, at 18:52, John Clark <johnkcl...@gmail.com> wrote: > > > > On Wed, Mar 10, 2021 at 5:56 PM Jason Resch <jasonre...@gmail.com > <mailto:jasonre...@gmail.com>> wrote: > > > I believe Chaitin has a definition of randomness that works for finite > > strings. If I remember correctly it has to do with the length of the > > shortest program that outputs the string being longer than the string > > itself. > > Yes, but that definition has one severe disadvantage. Mathematicians can > prove that they are an infinite number of finite strings of X length in which > there are no program shorter than X that could produce them, however there is > no way to prove in general that one particular string of length X is of that > nature.
Indeed. In fact Chaitin did prove a “new" incompleteness theorem, but unlike Gödel’s one, it is not constructive. No machine can prove the algorithmic randomness of sequence bigger than themselves (up to some constant related to its code length). I put “new” in quote, because that theorem was proved by Emil Post much before, but in a context having no relation with complexity of string, but with his notion of simple and immune set. It illustrates set whose logical complexity is between the recursive and the m-complete (or creative) sets (which are also Turing-complete). Randomness, unlike creativity or Turing-universality is a non constructive notion, which is as we could expect intuitively. Bruno > . > John K Clark See what's on my new list at Extropolis > <https://groups.google.com/g/extropolis> > > . > > > > -- > 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/CAJPayv2D-k2%3DA%2BY%3DT8SHQm-tgF7fpwmxRYvrc1Dt5VgQJ6CD2A%40mail.gmail.com > > <https://groups.google.com/d/msgid/everything-list/CAJPayv2D-k2%3DA%2BY%3DT8SHQm-tgF7fpwmxRYvrc1Dt5VgQJ6CD2A%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/17770171-F6DD-4035-9C99-1EEBDE3B132C%40ulb.ac.be.
