5 ms·

2 would be the wrong answer here, because K-complexity includes the definition of sha256 itself.

by p1mrx 5y ago

lisper 5y ago
This is a very good point and very important to understand. K-complexity is measured in terms of how many bits you need to specify a Turing machine (under some encoding) that computes the function. There are therefore only four functions whose K-complexity is 2. An important ancillary result is Chaitin's theorem, which is that beyond a certain threshold (a few hundred bits) it is not possible to know the K-complexity of a function because if you did then you could solve the halting problem. See [1] for a simple proof. [1] https://flownet.com/ron/chaitin.html https://flownet.com/ron/chaitin.html
- dmead 5y ago
  Which four functions?
  - rocqua 5y ago
    That would depend heavily on the encoding used for your turning machine.
    - JPLeRouzic 5y ago
      You probably mean a Dervish turning machine, with a halting problem?
  - not-my-account 5y ago
    00,01,10,11
- mxkopy 5y ago
  That article was incredibly good, especially the digression on determinism with Einstein, Born and Pauli. I feel like synchronicity just boils down to the pigeonhole principle.
- jychang 5y ago
  > Chaitin's theorem That's already mentioned in the original article. > There’s just one drawback to Kolmogorov complexity: It’s incomputable, meaning that there is no program that can calculate the complexity of every possible string. We know this because if there were such a program, we’d end up with a contradiction. > To see this, imagine we have a program that can compute Kolmogorov complexity for any string. Let’s call the program K. Now, let’s search for the smallest string of numbers — call it S — whose Kolmogorov complexity is double the length of K. To be concrete, we could imagine that K has 1 million characters, so we’re looking for a string S whose Kolmogorov complexity is 2 million (meaning that the shortest program that outputs S has 2 million characters). > With program K in our toolbox, calculating S is easy (though not necessarily quick): We can write a new program that we’ll call P. The program P essentially says, “Go through all strings in order, using program K to compute their Kolmogorov complexity, until you find the first one whose Kolmogorov complexity is 2 million.” We’ll need to use program K when building P, so altogether P will have slightly more than 1 million characters. But this program outputs S, and we defined S as a string whose shortest program has 2 million characters. There’s the contradiction.

2 would be the wrong answer here, because K-complexity includes the definition of sha256 itself.

by p1mrx 5y ago

2 would be the wrong answer here, because K-complexity includes the definition of sha256 itself.

This is a very good point and very important to understand. K-complexity is measured in terms of how many bits you need to specify a Turing machine (under some encoding) that computes the function. There are therefore only four functions whose K-complexity is 2. An important ancillary result is Chaitin's theorem, which is that beyond a certain threshold (a few hundred bits) it is not possible to know the K-complexity of a function because if you did then you could solve the halting problem. See [1] for a simple proof. [1] https://flownet.com/ron/chaitin.html https://flownet.com/ron/chaitin.html

dmead 5y ago
Which four functions?
- rocqua 5y ago
  That would depend heavily on the encoding used for your turning machine.
  - JPLeRouzic 5y ago
    You probably mean a Dervish turning machine, with a halting problem?
- not-my-account 5y ago
  00,01,10,11
mxkopy 5y ago
That article was incredibly good, especially the digression on determinism with Einstein, Born and Pauli. I feel like synchronicity just boils down to the pigeonhole principle.
jychang 5y ago
> Chaitin's theorem That's already mentioned in the original article. > There’s just one drawback to Kolmogorov complexity: It’s incomputable, meaning that there is no program that can calculate the complexity of every possible string. We know this because if there were such a program, we’d end up with a contradiction. > To see this, imagine we have a program that can compute Kolmogorov complexity for any string. Let’s call the program K. Now, let’s search for the smallest string of numbers — call it S — whose Kolmogorov complexity is double the length of K. To be concrete, we could imagine that K has 1 million characters, so we’re looking for a string S whose Kolmogorov complexity is 2 million (meaning that the shortest program that outputs S has 2 million characters). > With program K in our toolbox, calculating S is easy (though not necessarily quick): We can write a new program that we’ll call P. The program P essentially says, “Go through all strings in order, using program K to compute their Kolmogorov complexity, until you find the first one whose Kolmogorov complexity is 2 million.” We’ll need to use program K when building P, so altogether P will have slightly more than 1 million characters. But this program outputs S, and we defined S as a string whose shortest program has 2 million characters. There’s the contradiction.