Kolmogorov complexity relates to compression, which relies on modelling probability of future context with respect to previous context. Removing backwards branches is the easiest way to eliminate Turing completeness, which also lets one solve the halting problem.
Lazyweb, do any interesting things happen if you define an analogue of Kolmogorov complexity in terms of an explicitly non-Turing-complete description language?
-
-
-
Right. Something unboundedly-recursive is not a reasonable "compression" anyway. Certainly "decompressible in working space not larger than a small multiple of the uncompressed data" is a reasonable constraint.
-
Unfortunately I don't think many "interesting things happen" aside from breaking the formal logicians' toys, since all the relevant computations are way outside the scope of practical computability anyway once you reach a certain size.
-
But maybe there are some interesting results that can be had for moderately small sizes, e.g. on topics like password strength.
-
Ya, would the entropy of a program without backwards branches correlate with its output? PRF which without backwards branches would need to be unrolled to the length of its output. The program entropy would be extremely low.
End of conversation
New conversation -
-
-
A TC lang can't calculate Kolmogorov complexity, so why would defining a proof in terms of a non-TC lang be more enlightening :P?
-
You're missing the point. The set of programs over which the minimum is taken is in a non-TC language. The program computing the complexity is free to be in a TC language.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.