3 ms·

Confused how the interesting number paradox proves KC cannot be computed.

by causal 3y ago

srcreigh 3y ago
The author is referring to something called Chaitin incompleteness. https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin's_incompleteness_theorem https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin'... Of course trivially some KC can be proven, ex a language with 1 or 0 characters that is interpreted to a specific string. Or to prove KC(x) where the compressed value has length N and you can list out all the results for all strings of length less than N, and they don't equal x, proves KC(x)=N. The interesting number paradox (Berry's paradox) is more related to Chaitin incompleteness. Basically, given a language there’s some code which enumerates proofs that KC of a string is more than some constant L, and returns the first one it finds. If the constant L is large enough, it becomes larger than the entire proof generating code. So the proof generating code will never find a proof of any KC larger than L. It's interesting to think about that the language gets more complex, proofs for larger strings become possible. And what it would mean for the languages to keep getting more complex indefinitely. it's a similar train of thought to busy beaver numbers and how systems of logic (PA,ZFC) become independent to values like BB(745), and what it could mean to have more and more advanced types of logic which don't become independent until some high target n.
- causal 3y ago
  This seems to assume that KC can be infinite. That must have been proven at some point? Otherwise it may be that there is some upper-bound for L which happens to also be the KC for a KC-computer.
  - srcreigh 3y ago
    yes, it’s a pigeonhole principle argument. A bit tricky to actually enumerate everything. Imagine KC had a limit k. Then there’s a fixed number of strings that can be compressed to k characters. so considering how there’s an infinite number of strings of length greater than k, they can’t all be compressed to be at most k. Therefore KC has no limit
  - tromp 3y ago
    KC(x) is always finite for any finite x. What we can say instead is that KC is unbounded. I.e. there is no finite bound on the value of KC(x).
Opocio 3y ago
Me neither. But how I see it is that for solving KC in full generality you'll have to: - Start with the program that explicitly returns the original string. Let's say it has length N - run all possible programs that are shorter than N (just try all combinations of characters) - look at the results and pick the shortest program that compiles and outputs the original string The problem there is that you have to wait for all programs to end, and you don't know if they will end or not. So you have a problem that's equivalent to the halting problem (and that's not solvable) (and the halting problem is loosely related to the interesting number problem). (This is not a proof and I don't have a background in the field btw)
- causal 3y ago
  That intuitively makes sense to me.
nyrikki 3y ago
Impredicativity is the property you may want to dig into for formal proofs on why self references can be problematic. There is an important difference between semantically complete and syntactically complete that may cause some barriers. Gödels completeness theorem is about semantic completeness while his incompleteness theorems are about syntactic completeness. From Wikipedia: > A formal system is syntactically complete if and only if no unprovable sentence can be added to it without introducing an inconsistency. 'This statement is false', which Gödel mapped to natural numbers is an example of that inconsistency. If KC was computable, there would be an infinity of paradoxes like the interesting number paradox. The Berry paradox that is linked to in the INP link in the page has a subheading that relates it to KC computability. https://en.m.wikipedia.org/wiki/Berry_paradox https://en.m.wikipedia.org/wiki/Berry_paradox
explaininjs 3y ago
Similar to how the interesting number paradox relies on a "shortcut statement" to force-up the number of non-interest, If Kolmogorov complexity were computable you could create a "shortcut program" to force-down the shortest length of the program: Given: TM length of a JS runtime is 1,000,000 cells. Assume: KC is computable, and TM length of a `function KolmoglorovComplexity(string s)` is 4,000,000 cells. Known: KC's of values grow infinitely large - only 2^n-1 possible values can ever be encoded by n bits. Take: function Shortcut() { for (const s in generateEveryStringFromShortestUp()) { if ( KolomoglorovComplexity(s > 10,000,000) ) return s } } You see that the Shortcut function is encoded in 5,000,135 cells (plus that string generator, but that's small/constant), but it computes a value of arbitrarily large complexity (rather, one cell increase in the program length causes 10x increase in the complexity). A contradiction.
- causal 3y ago
  Still confused. What is contradictory about a simple program computing a more complex program? Randomly generating a more complex program does not make the complex program reducible to a random string generator.
  - basil-rash 3y ago
    The complexity cannot be over 10,000,000 if that simple program generated it. That is the precise definition of complexity. I don’t understand what you mean by reducibility to random strings, randomness has precisely nothing to do with complexity, even if they do tend to go together.
  - Dylan16807 3y ago
    > Randomly generating a more complex program does not make the complex program reducible to a random string generator. The complex program probably does something other than generate random strings. But the complex program is not actually more complex than the generator plus a smidge. Because anywhere you're using the complex(z), you can replace it with generator()(z).

Confused how the interesting number paradox proves KC cannot be computed.

by causal 3y ago

Confused how the interesting number paradox proves KC cannot be computed.

The author is referring to something called Chaitin incompleteness. https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin's_incompleteness_theorem https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin'... Of course trivially some KC can be proven, ex a language with 1 or 0 characters that is interpreted to a specific string. Or to prove KC(x) where the compressed value has length N and you can list out all the results for all strings of length less than N, and they don't equal x, proves KC(x)=N. The interesting number paradox (Berry's paradox) is more related to Chaitin incompleteness. Basically, given a language there’s some code which enumerates proofs that KC of a string is more than some constant L, and returns the first one it finds. If the constant L is large enough, it becomes larger than the entire proof generating code. So the proof generating code will never find a proof of any KC larger than L. It's interesting to think about that the language gets more complex, proofs for larger strings become possible. And what it would mean for the languages to keep getting more complex indefinitely. it's a similar train of thought to busy beaver numbers and how systems of logic (PA,ZFC) become independent to values like BB(745), and what it could mean to have more and more advanced types of logic which don't become independent until some high target n.

causal 3y ago
This seems to assume that KC can be infinite. That must have been proven at some point? Otherwise it may be that there is some upper-bound for L which happens to also be the KC for a KC-computer.
- srcreigh 3y ago
  yes, it’s a pigeonhole principle argument. A bit tricky to actually enumerate everything. Imagine KC had a limit k. Then there’s a fixed number of strings that can be compressed to k characters. so considering how there’s an infinite number of strings of length greater than k, they can’t all be compressed to be at most k. Therefore KC has no limit
- tromp 3y ago
  KC(x) is always finite for any finite x. What we can say instead is that KC is unbounded. I.e. there is no finite bound on the value of KC(x).

Opocio 3y ago

Me neither. But how I see it is that for solving KC in full generality you'll have to: - Start with the program that explicitly returns the original string. Let's say it has length N - run all possible programs that are shorter than N (just try all combinations of characters) - look at the results and pick the shortest program that compiles and outputs the original string The problem there is that you have to wait for all programs to end, and you don't know if they will end or not. So you have a problem that's equivalent to the halting problem (and that's not solvable) (and the halting problem is loosely related to the interesting number problem). (This is not a proof and I don't have a background in the field btw)

causal 3y ago
That intuitively makes sense to me.

nyrikki 3y ago

Impredicativity is the property you may want to dig into for formal proofs on why self references can be problematic. There is an important difference between semantically complete and syntactically complete that may cause some barriers. Gödels completeness theorem is about semantic completeness while his incompleteness theorems are about syntactic completeness. From Wikipedia: > A formal system is syntactically complete if and only if no unprovable sentence can be added to it without introducing an inconsistency. 'This statement is false', which Gödel mapped to natural numbers is an example of that inconsistency. If KC was computable, there would be an infinity of paradoxes like the interesting number paradox. The Berry paradox that is linked to in the INP link in the page has a subheading that relates it to KC computability. https://en.m.wikipedia.org/wiki/Berry_paradox https://en.m.wikipedia.org/wiki/Berry_paradox

explaininjs 3y ago

Similar to how the interesting number paradox relies on a "shortcut statement" to force-up the number of non-interest, If Kolmogorov complexity were computable you could create a "shortcut program" to force-down the shortest length of the program: Given: TM length of a JS runtime is 1,000,000 cells. Assume: KC is computable, and TM length of a `function KolmoglorovComplexity(string s)` is 4,000,000 cells. Known: KC's of values grow infinitely large - only 2^n-1 possible values can ever be encoded by n bits. Take: function Shortcut() { for (const s in generateEveryStringFromShortestUp()) { if ( KolomoglorovComplexity(s > 10,000,000) ) return s } } You see that the Shortcut function is encoded in 5,000,135 cells (plus that string generator, but that's small/constant), but it computes a value of arbitrarily large complexity (rather, one cell increase in the program length causes 10x increase in the complexity). A contradiction.

causal 3y ago
Still confused. What is contradictory about a simple program computing a more complex program? Randomly generating a more complex program does not make the complex program reducible to a random string generator.
- basil-rash 3y ago
  The complexity cannot be over 10,000,000 if that simple program generated it. That is the precise definition of complexity. I don’t understand what you mean by reducibility to random strings, randomness has precisely nothing to do with complexity, even if they do tend to go together.
- Dylan16807 3y ago
  > Randomly generating a more complex program does not make the complex program reducible to a random string generator. The complex program probably does something other than generate random strings. But the complex program is not actually more complex than the generator plus a smidge. Because anywhere you're using the complex(z), you can replace it with generator()(z).