3 ms·

This makes sense, intuitively; if I gave you "8f434346648f6b96df89dda901c5176b10a6d83961dd3c1ac88b59b2dc327aa4" (sha256('hi')), and you quickly told me its K co

This makes sense, intuitively; if I gave you "8f434346648f6b96df89dda901c5176b10a6d83961dd3c1ac88b59b2dc327aa4" (sha256('hi')), and you quickly told me its K complexity was 2, I would become skeptical that sha256 was a one way function. (assuming of course you didn't brute force it)

rogers18445 5y ago
The correct analogy would be suppose I give you a block of an encrypted uncompressed image. And you return K(encryption_algo_with_key) + K(image_compression_algo_with_compressed_image)
mxkopy 5y ago
My intuition was this: Take a sequence of operations (AND, OR, NOT) and assign each unique term a prime, then multiply each term by some other prime raised to their respective position in the sequence. Call the result the 'output'. This kinda feels like running a program. Now, try and work out, for any given output, the sequence of minimum operations & their order that would get that output. Basically you factor, which is a common 'one-way' function from my understanding. P.S. I feel like the multiplied sequence of operations is a program, but then adding some input (encoded as a number) to that is closer to actually running the program. Then, for every output you have a unique program P with input 0 that gives you that output, but P isn't necessarily tied to the structure of the original program that generated that specific output.
p1mrx 5y ago
2 would be the wrong answer here, because K-complexity includes the definition of sha256 itself.
- 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.

rogers18445 5y ago

The correct analogy would be suppose I give you a block of an encrypted uncompressed image. And you return K(encryption_algo_with_key) + K(image_compression_algo_with_compressed_image)

mxkopy 5y ago

My intuition was this: Take a sequence of operations (AND, OR, NOT) and assign each unique term a prime, then multiply each term by some other prime raised to their respective position in the sequence. Call the result the 'output'. This kinda feels like running a program. Now, try and work out, for any given output, the sequence of minimum operations & their order that would get that output. Basically you factor, which is a common 'one-way' function from my understanding. P.S. I feel like the multiplied sequence of operations is a program, but then adding some input (encoded as a number) to that is closer to actually running the program. Then, for every output you have a unique program P with input 0 that gives you that output, but P isn't necessarily tied to the structure of the original program that generated that specific output.

p1mrx 5y ago

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

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.