3 ms·
The value of K for any language is within a constant of K for any other language. To convince yourself this is true, imagine constructing an interpreter for you
by tlb 5y ago
The value of K for any language is within a constant of K for any other language. To convince yourself this is true, imagine constructing an interpreter for your preferred language in whatever language you are given. You can always prepend this (fixed-sized) interpreter to a program in your preferred language, adding a constant value to the complexity.
- pishpash 5y agoK can be arbitrarily large though.
- Ono-Sendai 5y agoYes, 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 agoYes, but still finite.
- pishpash 5y agoAs 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 agoI 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 ago1+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 agoWhat 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?
- dvt 5y agoHah, this is a very clever way of putting it. Will certainly use this thought experiment in the future! :)
- Xcelerate 5y agoThis is known as the invariance theorem: https://en.m.wikipedia.org/wiki/Kolmogorov_complexity#Invariance_theorem https://en.m.wikipedia.org/wiki/Kolmogorov_complexity#Invari...