26 ms·

I’ll ask it here since I’ve not seen it mentioned anywhere: the Kolmogorov work is interesting, but doesn’t it exclude the information necessary to produce a te

by svnt 4y ago

I’ll ask it here since I’ve not seen it mentioned anywhere: the Kolmogorov work is interesting, but doesn’t it exclude the information necessary to produce a team of educated humans, a universal computer, a programming language, and a compiler/interpreter, at least? In a brief reading AIT seems to assume a universal Turing machine should exist by natural law.

ttctciyf 4y ago
Regards the interpreter aspect, that is dealt with by fixing some universal Turing machine - call it U - which runs all the programs considered, so that the program length of U becomes a constant which can either be factored out or reduced to insignificance by considering programs and strings with length much greater than U's. It is still a fly in the theoretical ointment that the K complexity of a given specific string might differ under different choices of U, not least because programs that encode some string might find chunks of it inside a specific U, like a program which prints the BIOS signon of a particular firmware could be shorter when running on that firmware. Regards the biological / sociological aspects you mention, I think the theoretical framework requires only the bare existence of some UTM with a finite size. If it is really Universal, you could just run the program which produces human society on it until we reach the present, I guess :)
- svnt 4y ago
  Ha! Thanks for your insights. It does seem like a significant gap between the theory/maths and the implementation.
dawnofdusk 4y ago
There is no problem with assuming such a Turing machine exists so long as you compare only measurements of information with respect to that Turing machine. Generally what is relevant to study is entropy differences anyway. I don't know much about AIT in specific, but it seems that Chaitin 1975 (https://dl.acm.org/doi/10.1145/321892.321894 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) https://en.wikipedia.org/wiki/Maxwell's_demon).
- svnt 4y ago
  Thanks very much for the pointer to the paper and ideas. I am quite interested in artificial life and the information theoretical + biophysics view on that is something I’ll enjoy looking into.
rcxdude 4y ago
It's a mostly theoretical concept so when making comparisons you can pick whatever machine you want, pretty much. Actual compression contests (like the hutter prize: http://prize.hutter1.net/ http://prize.hutter1.net/) will pick a particular platform and configuration to run on.

by svnt 4y ago

ttctciyf 4y ago

Regards the interpreter aspect, that is dealt with by fixing some universal Turing machine - call it U - which runs all the programs considered, so that the program length of U becomes a constant which can either be factored out or reduced to insignificance by considering programs and strings with length much greater than U's. It is still a fly in the theoretical ointment that the K complexity of a given specific string might differ under different choices of U, not least because programs that encode some string might find chunks of it inside a specific U, like a program which prints the BIOS signon of a particular firmware could be shorter when running on that firmware. Regards the biological / sociological aspects you mention, I think the theoretical framework requires only the bare existence of some UTM with a finite size. If it is really Universal, you could just run the program which produces human society on it until we reach the present, I guess :)

svnt 4y ago
Ha! Thanks for your insights. It does seem like a significant gap between the theory/maths and the implementation.

dawnofdusk 4y ago

There is no problem with assuming such a Turing machine exists so long as you compare only measurements of information with respect to that Turing machine. Generally what is relevant to study is entropy differences anyway. I don't know much about AIT in specific, but it seems that Chaitin 1975 (https://dl.acm.org/doi/10.1145/321892.321894 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) https://en.wikipedia.org/wiki/Maxwell's_demon).

svnt 4y ago
Thanks very much for the pointer to the paper and ideas. I am quite interested in artificial life and the information theoretical + biophysics view on that is something I’ll enjoy looking into.

rcxdude 4y ago

It's a mostly theoretical concept so when making comparisons you can pick whatever machine you want, pretty much. Actual compression contests (like the hutter prize: http://prize.hutter1.net/ http://prize.hutter1.net/) will pick a particular platform and configuration to run on.