• m_‮f@discuss.onlineOP
      30·
      2 days ago

      https://en.wikipedia.org/wiki/Kolmogorov_complexity

      In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963 and is a generalization of classical information theory.

      Put another way, it’s a measure of how compressible information is. If you have a file that’s 1 GB, but it’s all 0’s, you can compress that down to 4 bytes by simply storing the number of 0’s. On the flip side, random data can’t really be meaningfully compressed.

      Another example from the link:

      This image illustrates part of the Mandelbrot set fractal. Simply storing the 24-bit color of each pixel in this image would require 23 million bytes, but a small computer program can reproduce these 23 MB using the definition of the Mandelbrot set, the corner coordinates of the image and the parameters of the color mapping. Thus, the Kolmogorov complexity of this image is much less than 23 MB in any pragmatic model of computation. PNG’s general-purpose image compression only reduces it to 1.6 MB, smaller than the raw data but much larger than the Kolmogorov complexity.

      • shevek@lemmy.dbzer0.com
        3·
        1 day ago

        Weird, I just encountered Kolmogorov and Shannon complexity while reading Exordia last night.

        “Shannon entropy is how much information you need to describe a thing. Kolomogorov entropy is how much information you need to write down instructions to make that thing.”

        • m_‮f@discuss.onlineOP
          5·
          2 days ago

          Apparently not:

          https://math.stackexchange.com/a/3680805

          Shannon Entropy is about compression of (long) words generated by biased die toss. And if dice entropy is H, we can’t (on average) compress results of n tosses to less than n⋅H bits.

          Kolmogorov Complexity is about compression of arbitrary words. Of course, if word is generated by the same die, it’s average complexity will be n⋅H+O(1).

          • tetris11@feddit.ukEnglish
            4·
            2 days ago

            Of course, if word is generated by the same die, it’s average complexity will be n⋅H+O(1).

            Of course.

    • Padit@feddit.org
      10·
      2 days ago

      The only thing i know about Kolmogorov is thst his dissertstion was published in German, despite him beeing Russian.

      My math teacher once said that. I forgot the rest.

    • NeatNit@discuss.tchncs.de
      5·
      2 days ago

      I really can’t figure out what Zach intended for this to mean. Year is defined but never used: you’d expect something like books(year) instead of just books(). I have absolutely no idea what the function calls are supposed to represent.

      • wolframhydroxide@sh.itjust.works
        1·
        12 hours ago

        I think that “books”, “gardening” and “family” were meant to be functions, each of which was called each year over the 88 year lifespan.

        • NeatNit@discuss.tchncs.de
          1·
          12 hours ago

          It effectively runs:

          books(); gardening(); family()
books(); gardening(); family()
books(); gardening(); family()
books(); gardening(); family()
books(); gardening(); family()
books(); gardening(); family()
...

          it runs those 3 functions 88 times, there’s no hint as to what they do.

          • wolframhydroxide@sh.itjust.works
            1·
            6 hours ago

            We aren’t given the full eulogy in the comic, only the first lines of the main function. I imagine that it would continue with defining the functions.

    • m_‮f@discuss.onlineOP
      2·
      2 days ago

      Apart from the indentation issue (and semantics identified in sibling comment), the joke works in python:

      >>> for i in range(3):
...     print(i, end=' '); print(i**2, end=' '); print(i**3)
...
0 0 0
1 1 1
2 4 8