4 ms·

K can be arbitrarily large though.

Ono-Sendai 5y ago
Yes, in my view you are entirely right, Kolmogorov complexity says nothing about any complexity independent of language. The invariance theorem is true, but useless: https://forwardscattering.org/post/14 https://forwardscattering.org/post/14
dvt 5y ago
Yes, but still finite.
- pishpash 5y ago
  As in the above comment, the K constant actually bears on low-complexity strings, not high-complexity ones. It says low-complexity strings in any language are always reasonably low-complexity (within +K) in other languages, but since K can be arbitrarily large, the bound is totally loose and useless.
isotropy 5y ago
I think the key is that K is fixed per language, not per input. So if you have a sequence of inputs of complexity 1, 10, 100, 1000, 10000...in language L1, then in language L2, the complexities will be something like 1+K, 10+K, 100+K, 1000+K, 10000+K,.... In the limit of very-high-complexity-input (pick a random TB of data as your string) the language-specific constant is overwhelmed.
- pishpash 5y ago
  1+K, 10+K, ... are merely upper bounds on the Kolmogorov complexities in L2, but the actual complexities can be lower, by an arbitrary amount for some strings. Furthermore, what's considered complex in L1 and L2 can be very different, and although "most" strings would be complex in either language, they don't have to be the same subsets in L1 and L2.
  - westurner 5y ago
    What is the correlation between _ complexity and e.g. EVM/eWASM opcode [CPU,] costs? https://news.ycombinator.com/item?id=28499001 https://news.ycombinator.com/item?id=28499001 > Smart contracts cost CPU usage with costed opcodes. eWASM (Ethereum WebAssembly) has costed opcodes for redundantly-executed smart contracts (that execute on n nodes of a shard) https://ewasm.readthedocs.io/en/mkdocs/determining_wasm_gas_costs/#gas-costs-of-individual-instructions https://ewasm.readthedocs.io/en/mkdocs/determining_wasm_gas_... > AFAIU, while there are DLTs that cost CPU, RAM, and Data storage between points in spacetime, none yet incentivize energy efficiency by varying costs depending upon whether the instructions execute on a FPGA, ASIC, CPU, GPU, TPU, or QPU?

Yes, in my view you are entirely right, Kolmogorov complexity says nothing about any complexity independent of language. The invariance theorem is true, but useless: https://forwardscattering.org/post/14 https://forwardscattering.org/post/14

dvt 5y ago

Yes, but still finite.

pishpash 5y ago
As in the above comment, the K constant actually bears on low-complexity strings, not high-complexity ones. It says low-complexity strings in any language are always reasonably low-complexity (within +K) in other languages, but since K can be arbitrarily large, the bound is totally loose and useless.

isotropy 5y ago

I think the key is that K is fixed per language, not per input. So if you have a sequence of inputs of complexity 1, 10, 100, 1000, 10000...in language L1, then in language L2, the complexities will be something like 1+K, 10+K, 100+K, 1000+K, 10000+K,.... In the limit of very-high-complexity-input (pick a random TB of data as your string) the language-specific constant is overwhelmed.

pishpash 5y ago
1+K, 10+K, ... are merely upper bounds on the Kolmogorov complexities in L2, but the actual complexities can be lower, by an arbitrary amount for some strings. Furthermore, what's considered complex in L1 and L2 can be very different, and although "most" strings would be complex in either language, they don't have to be the same subsets in L1 and L2.
- westurner 5y ago
  What is the correlation between _ complexity and e.g. EVM/eWASM opcode [CPU,] costs? https://news.ycombinator.com/item?id=28499001 https://news.ycombinator.com/item?id=28499001 > Smart contracts cost CPU usage with costed opcodes. eWASM (Ethereum WebAssembly) has costed opcodes for redundantly-executed smart contracts (that execute on n nodes of a shard) https://ewasm.readthedocs.io/en/mkdocs/determining_wasm_gas_costs/#gas-costs-of-individual-instructions https://ewasm.readthedocs.io/en/mkdocs/determining_wasm_gas_... > AFAIU, while there are DLTs that cost CPU, RAM, and Data storage between points in spacetime, none yet incentivize energy efficiency by varying costs depending upon whether the instructions execute on a FPGA, ASIC, CPU, GPU, TPU, or QPU?