If you could compute them, you could use that computation (in a complicated way) to produce strings that could only be produced by much longer programs. This is a contradiction, so it’s not possible to compute complexity.
And I guess you can’t just enumerate all programs and take the length of the shortest (=first) one that produces the string because of the halting problem?
I wonder if I could turn that around and spin a computation of complexity into a halting oracle...
So, any string can be made by some programs, each program has a mathematical complexity of K, we say each string has a K of the program with the smallest K that makes that string. If knowing a string gives us a precise value for K, knowing a precise value for K lets us generate some strings that are more complex than K but no more complex than any other strings higher than K. Some strings are random, and have Ks that are strings more complex than the strings they describe. For some string the shortest program that makes it will be “The shortest string with K greater than K1”, and “The shortest string with K greater than K1″ is a program with a low K. Yet that string was chosen by the program because it had a higher K than “the shortest string with complexity greater than K” does, so the string thus delineated “really” has a very small K, not a high one, so it must be unselected, and thus unselected it “really” has a high K again, falsifying that program’s selection of anything else.
The problem is that programs can be made out of self referencing words that select their components and targets based on what other programs are doing.
Can’t we still calculate K in a mathematical universe forbidding self referencing sentences? In our world we are comfortable saying K1 is greater than K2 if and only if we know it is orders of magnitude greater. What would be wrong with saying K1 is greater than K2 because K1=100 and K2=10, where K is complexity in the mathematical world with the extra axiom?
Can’t we still calculate K* in a mathematical universe forbidding self referencing sentences?
I’m not mathematician enough to say yes, but I think so. I don’t know how well/simple a no-self-reference version of some theories stacks up against the self-referencing versions (I am in the mind of lisp’s recursion features; without that ability lisp programs would be … longer and more complicated).
For every string there is a program that gives it its smallest k, s+p=K.
For every s there is a k bigger than s but no bigger than any other k, yet
“For some sn there is a Kn bigger than sn but no bigger than any other K” < pn?
So computing K for every s means there is a paradox for some s.
Can we make our lives easy by picking a s, accepting it is a paradox, and moving on to compute all other Ks? Or more intensely, by randomly picking a representative sample of strings to be paradoxes, calculate each (non-paradox) string’s K in each paradox world, and then average out the Ks?
It seems like Eliezer only affirmatively says one K is bigger than another when they are of vastly different orders of magnitude.
If this is obviously wrong, sorry but I have no math background!
Any string can be made by some programs, each program has a mathematical complexity of K, we say each string has a K of the program with the smallest K that makes that string. If knowing a string gives us a precise value for K, knowing a precise value for K lets us generate some strings that are more complex than K but no more complex than any other strings higher than K. Some strings are random, and have Ks that are strings more complex than the strings they describe. For some string the shortest program that makes it will be “The shortest string with K greater than K1”, and “The shortest string with K greater than K1″ is a program with a low K. Yet that string was chosen by the program because it had a higher K than “the shortest string with complexity greater than K” does, so the string thus delineated “really” has a very small K, not a high one, so it must be unselected, and thus unselected it “really” has a high K again, falsifying that program’s selection of anything else.
The problem is that programs can be made out of self referencing words that select their components and targets based on what other programs are doing.
Can’t we still calculate K in a mathematical universe forbidding self referencing sentences? In our world we are comfortable saying K1 is greater than K2 if and only if we know it is orders of magnitude greater. What would be wrong with saying K1 is greater than K2 because K1=100 and K2=10, where K is complexity in the mathematical world with the extra axiom?
If you could compute them, you could use that computation (in a complicated way) to produce strings that could only be produced by much longer programs. This is a contradiction, so it’s not possible to compute complexity.
And I guess you can’t just enumerate all programs and take the length of the shortest (=first) one that produces the string because of the halting problem?
I wonder if I could turn that around and spin a computation of complexity into a halting oracle...
So, any string can be made by some programs, each program has a mathematical complexity of K, we say each string has a K of the program with the smallest K that makes that string. If knowing a string gives us a precise value for K, knowing a precise value for K lets us generate some strings that are more complex than K but no more complex than any other strings higher than K. Some strings are random, and have Ks that are strings more complex than the strings they describe. For some string the shortest program that makes it will be “The shortest string with K greater than K1”, and “The shortest string with K greater than K1″ is a program with a low K. Yet that string was chosen by the program because it had a higher K than “the shortest string with complexity greater than K” does, so the string thus delineated “really” has a very small K, not a high one, so it must be unselected, and thus unselected it “really” has a high K again, falsifying that program’s selection of anything else.
The problem is that programs can be made out of self referencing words that select their components and targets based on what other programs are doing.
Can’t we still calculate K in a mathematical universe forbidding self referencing sentences? In our world we are comfortable saying K1 is greater than K2 if and only if we know it is orders of magnitude greater. What would be wrong with saying K1 is greater than K2 because K1=100 and K2=10, where K is complexity in the mathematical world with the extra axiom?
I’m not mathematician enough to say yes, but I think so. I don’t know how well/simple a no-self-reference version of some theories stacks up against the self-referencing versions (I am in the mind of lisp’s recursion features; without that ability lisp programs would be … longer and more complicated).
Is this right:
For every string there is a program that gives it its smallest k, s+p=K. For every s there is a k bigger than s but no bigger than any other k, yet “For some sn there is a Kn bigger than sn but no bigger than any other K” < pn?
So computing K for every s means there is a paradox for some s.
Can we make our lives easy by picking a s, accepting it is a paradox, and moving on to compute all other Ks? Or more intensely, by randomly picking a representative sample of strings to be paradoxes, calculate each (non-paradox) string’s K in each paradox world, and then average out the Ks?
It seems like Eliezer only affirmatively says one K is bigger than another when they are of vastly different orders of magnitude.
If this is obviously wrong, sorry but I have no math background!
Allow me to try again.
Any string can be made by some programs, each program has a mathematical complexity of K, we say each string has a K of the program with the smallest K that makes that string. If knowing a string gives us a precise value for K, knowing a precise value for K lets us generate some strings that are more complex than K but no more complex than any other strings higher than K. Some strings are random, and have Ks that are strings more complex than the strings they describe. For some string the shortest program that makes it will be “The shortest string with K greater than K1”, and “The shortest string with K greater than K1″ is a program with a low K. Yet that string was chosen by the program because it had a higher K than “the shortest string with complexity greater than K” does, so the string thus delineated “really” has a very small K, not a high one, so it must be unselected, and thus unselected it “really” has a high K again, falsifying that program’s selection of anything else.
The problem is that programs can be made out of self referencing words that select their components and targets based on what other programs are doing.
Can’t we still calculate K in a mathematical universe forbidding self referencing sentences? In our world we are comfortable saying K1 is greater than K2 if and only if we know it is orders of magnitude greater. What would be wrong with saying K1 is greater than K2 because K1=100 and K2=10, where K is complexity in the mathematical world with the extra axiom?