Warning: Vague, unclear question ahead. Proceed at your own risk.

The Shannon entropy and Kolmogorov complexity give you in broad informal terms how unpredictable a string is and to what degree the data in a string can be compressed, respectively. What I want to do is to broaden those terms to try to encapsulate the complexity of a certain computer, of a program; is there already some information-theoretic metric that's capable of that?

It seems to me that the answer is buried somewhere in algorithmic information theory, but I don't know. I think that one way to do it would be to work from possible input and output strings, to say that the conditional Kolmogorov complexity between the program's input and output strings is the real essence of the complexity of the computation it carries out. So basically, I think the real information contained by a computer might be somehow related to the matrix of conditional Kolmogorov complexities relating every possible input to every possible output. But that's a long (possibly infinite) and messy description, and you could never even approximate it for any practical computer. Or at least I'd have absolutely no idea how.

The point of all this is that I'm trying to just begin to get my head around formalizing the idea of damage to a computer, of exactly how that damage can lead to information loss/loss of computational ability. In really broad strokes, I want an entirely formal way to say that the array of semiconductors that forms a calculator is more complex than an array of semiconductors forming a calculator with a lower precision, less operations, and a lower overflow value, which is more complex than an array of dust particles incapable of any practical computation. Are the vague ideas I just outlined a reasonable way to think about that concept? Or is there an already-existing sort of metric that could save me time?

  • $\begingroup$ The conditional complexity of the output string conditioned on the input string is at most roughly the complexity of the program itself, because that program can be used to turn the input into the output and can be described by a program of length equal to its complexity. $\endgroup$ – Solomonoff's Secret Nov 19 '14 at 19:53
  • $\begingroup$ You might want to check out circuit complexity, but for size and depth. $\endgroup$ – dtldarek Nov 19 '14 at 19:56
  • $\begingroup$ Circuit complexity might work, but you'd need to get a notion of probability in there somehow. Like, a high-entropy program could output absolutely anything, but the outputs are random and probably devoid of meaning. So imagine a perfect random number generator where whatever input you put in, it outputs 0 or 1 with 50% probability. From the circuit complexity perspective, where would you go with that? (I guess that's a problem underlying Kolmogorov complexity too, though - you can never really tell the difference between a random string and a complex pseudorandom one.) $\endgroup$ – Billy Smith Nov 19 '14 at 20:18
  • $\begingroup$ If it's just a finite array of semiconductors, you might want to consider a finite-state automaton. If you want probability, maybe consider a Markov model. $\endgroup$ – ShyPerson Dec 2 '14 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.