Lazyweb, do any interesting things happen if you define an analogue of Kolmogorov complexity in terms of an explicitly non-Turing-complete description language?
-
-
Replying to @RichFelker
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?
1 reply 0 retweets 0 likes
Replying to @cr1901
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.
9:55 AM - 5 May 2018
0 replies
0 retweets
1 like
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.