353 karma · joined September 8, 2022
>I am going to ask you elementary mathematics problems formulated in natural language. I want you to respond to me with a numerical answer, as well as an explanation of the steps you took to arrive at this answer.
And then follow it with a problem of your choice which is not completely trivial. For example, it has lots of trouble with the following: "John is in a train moving west at ten miles per hour. Jill is in a train moving north at twenty miles per hour. How fast are John and Jill moving apart from each other?" or a slightly more complicated problem, taken from the MATH dataset: "Tom has a red marble, a green marble, a blue marble, and three identical yellow marbles. How many different groups of two marbles can Tom choose?"
>strictly speaking the shortest possible encoding of a sequence of bits could be smaller than this would suggest, since it's possible a pattern exists that has escaped notice.
If it is a deterministic pattern, then the entropy of the sequence is actually 0. Otherwise the existence of patterns is something that the entropy computation already takes into account, and is in fact the entire point. In practice, finite sample sizes introduces noise and means that we can only ever estimate the true entropy, and Jensen's inequality implies that all such estimates are higher than the true entropy of a system, so that we observe even deterministic sequences with noisy filters. This is perhaps the clearer version of your point.
I don't know much about AIT in specific, but it seems that Chaitin 1975 (https://dl.acm.org/doi/10.1145/321892.321894) acknowledges this, as the algorithmic entropy differs from the usual Shannon entropy by a constant term, which one might imagine is the information needed to encode the Turing machine.
I also wanted to mention that because you thought of the information theoretic implications of building a computer, etc., you might be interested to know that this kind of thinking is very interesting and cutting edge in biophysics. Organisms have to essentially build computers to do certain tasks, and in this way they must take into account both Shannon entropy (i.e., information in the abstract sense) and thermodynamic entropy! This is essentially the Maxwell's demon paradox (https://en.wikipedia.org/wiki/Maxwell's_demon).