Hacker News new | ask | show | jobs
by yohanatan 4636 days ago
I don't think it is different actually. 'Kolmogorov complexity' (which is essentially the global minimum 'essential complexity' of a particular algorithm) is specified in terms of length.
1 comments

Applying Kolmogorov complexity in this context is a bit more tricky than you make it appear. Kolmogorov complexity measures the complexity of a string as the length of the shortest possible program that generates that string.

So to measure the complexity of a program P we have to write another program G that generates P and then take G's length. It's not a given that a generator for a verbose language is necessarily longer than a generator for a terse language.

But more importantly, what we want to measure is the mental effort required to write and understand code in different languages. To measure that effort in terms of Kolmogorov complexity, we'd have to write a program that generates our states of mind while programming.

Good luck with that ;-)

Actually, given a Turing Machine M which outputs x when given x, then we would have the description of program T0 (for terse language T) equal to the concatenation of the [specification of the] machine M with T0, M T0. Given program J1 (for verbose language J), its description equals M J1. Given sufficiently small M and large T0, the M factor's importance is quite reduced and we see that Kolmogorov complexity is roughly analogous to the respective sizes of T0 and J1 themselves (for this specific Turing Machine M).
You're forgetting that Kolmogorov complexity is the shortest possible description, not just any description of the desired output. The concatenation you're suggesting is highly unlikely to be the shortest possible one.

You have to think of it in terms of compression, because that's what Kolmogorov complexity is really about. It is certainly possible that after compression J1 is shorter than T0.

You're forgetting that I get to pick the Turing machine to use. Kolmogorov complexity is the shortest possible description relative to a particular Turing machine. Re-read my previous post with that in mind.
No you don't get to pick the particular Turing machine if by "particular Turing machine" you mean a Turing machine including a particular transition function, which is the conventional definition of Turing machine (http://en.wikipedia.org/wiki/Turing_machine#Formal_definitio...)

In terms of this definition we need two Turing machines, one whose transition function can be proven to be the shortest that describes L1. And another one whose transition function can be proven to be the shortest that describes T0. These two Turing machines or transition functions are compressed representations of L1 and T0 respectively.

What I'm saying is that the one describing L1 can be shorter than the one describing T0 even if L1 is longer than T0.

I think we are approaching this from different angles. I am thinking of a single contrived M for whom a simple copy input to output is the primary supported operation and all other operations/modes, although still capable of performing arbitrary computation [hence able to execute 'compressed' programs if you should wish to attempt to provide them and also, by definition, still Turing complete], are exceedingly clumsy/verbose.

I have not only the transition function but 6 other entities to define to accomplish this (really 5 barring the 'blank symbol') so I am certain that it is not only possible but likely much smaller than one might think at first. With such a small M (that penalizes attempts to compress T0 and J1), and a large T0 [such as the code base for Microsoft Windows ported to F#] and an even larger J1 [such as the same code base written in C], we still see my desired result.