4 ms·

Counterpoint (from my blog): http://forwardscattering.org/post/7 http://forwardscattering.org/post/7 http://forwardscattering.org/post/14 http://forwardscatte

Counterpoint (from my blog): http://forwardscattering.org/post/7 http://forwardscattering.org/post/7 http://forwardscattering.org/post/14 http://forwardscattering.org/post/14 In summary i don't think AIT offers an absolute measure of complexity, due to having to choose the abstract machine. Not to say the ideas aren't interesting, and that this isn't a nice article, from one of the main figures in the field.

joe_the_user 11y ago
I don't think your claims are correct. If you read a formal definition of Chaitin-Kolmogorov, you can find that the concept are essentially normalized by recursive function theory. By using the Church-Turing thesis, you can see that any program in any language can be simulated up to a constant length-multiple by an abstract Turing machine (speed isn't considered in these definitions so architecture doesn't matter much). Chaintin-Kolmogorov basically considers the log of the length of programs and then thus takes it's values as being plus or minus a constant for a given measure.
- Ono-Sendai 11y ago
  have a look at the second post, i address that.
  - mafribe 11y ago
    I'm sorry to say this, but your second post also doesn't really address the issue and continues to misunderstand the purpose and definitions of Kolgomorov complexity. The fact that for any specific string S you can find a language L such that the Kolgomorov complexity K(L, S) is 0, is not that interesting. 1. For any specific L, you can only play this trick (hardcoding a target string) for a finite number of strings. That means for essentially all strings (all but a small finite number) the trick is irrelevant. 2. There is no free lunch: The trick you use to bring down the Kolgomorov complexity K(L, S) down to 0 increases the complexity of L. This can be taken into account, see "conditional Kolgomorov complexity". The book "An Introduction to Kolmogorov Complexity and Its Applications" by Li and Vitányi explains this, and much more in great detail, and is highly recommended.
    - Ono-Sendai 11y ago
      Regarding point 2, I agree, but the question is how to measure the increase in complexity - we are back at square one :)
      - mafribe 11y ago
        You measure it in the same way, using the idea of shortest decription w.r.t. a fixed universal language. You than show that this is absolute up to a constant. Any results produced that way such as the incompressibility of most strings is independent of such constants, hence the the choice of universal language doesn't matter.
tromp 11y ago
You're confusing the statement "The Kolgomorov complexity of all strings is zero" with "For every string there exists a definition of Kolmogorov complexity in which that string has complexity 0" The first (which you claim as a Theorem) presumes an already fixed definition of complexity, and is therefore false, while the second is what you proof, and which is not interesting. Here's how I would fix the definition of Kolmogorov Complexity: https://en.wikipedia.org/wiki/Binary_lambda_calculus https://en.wikipedia.org/wiki/Binary_lambda_calculus

joe_the_user 11y ago

I don't think your claims are correct. If you read a formal definition of Chaitin-Kolmogorov, you can find that the concept are essentially normalized by recursive function theory. By using the Church-Turing thesis, you can see that any program in any language can be simulated up to a constant length-multiple by an abstract Turing machine (speed isn't considered in these definitions so architecture doesn't matter much). Chaintin-Kolmogorov basically considers the log of the length of programs and then thus takes it's values as being plus or minus a constant for a given measure.

Ono-Sendai 11y ago
have a look at the second post, i address that.
- mafribe 11y ago
  I'm sorry to say this, but your second post also doesn't really address the issue and continues to misunderstand the purpose and definitions of Kolgomorov complexity. The fact that for any specific string S you can find a language L such that the Kolgomorov complexity K(L, S) is 0, is not that interesting. 1. For any specific L, you can only play this trick (hardcoding a target string) for a finite number of strings. That means for essentially all strings (all but a small finite number) the trick is irrelevant. 2. There is no free lunch: The trick you use to bring down the Kolgomorov complexity K(L, S) down to 0 increases the complexity of L. This can be taken into account, see "conditional Kolgomorov complexity". The book "An Introduction to Kolmogorov Complexity and Its Applications" by Li and Vitányi explains this, and much more in great detail, and is highly recommended.
  - Ono-Sendai 11y ago
    Regarding point 2, I agree, but the question is how to measure the increase in complexity - we are back at square one :)
    - mafribe 11y ago
      You measure it in the same way, using the idea of shortest decription w.r.t. a fixed universal language. You than show that this is absolute up to a constant. Any results produced that way such as the incompressibility of most strings is independent of such constants, hence the the choice of universal language doesn't matter.

tromp 11y ago

You're confusing the statement "The Kolgomorov complexity of all strings is zero" with "For every string there exists a definition of Kolmogorov complexity in which that string has complexity 0" The first (which you claim as a Theorem) presumes an already fixed definition of complexity, and is therefore false, while the second is what you proof, and which is not interesting. Here's how I would fix the definition of Kolmogorov Complexity: https://en.wikipedia.org/wiki/Binary_lambda_calculus https://en.wikipedia.org/wiki/Binary_lambda_calculus