Hacker News new | ask | show | jobs
by sadgit 2878 days ago
> the shortest program that outputs "0" is "0".

Im tempted to debate this... in any programming language you need to use some space to differentiate a literal from code to be executed. So, according to Kolmogorov complexity, wouldn’t the shortest program to print a random number (or 0) be larger than that number?
1 comments
nl 2878 days ago
No, you can conceive a language which echos everything unless it is prefixed with an operator indicator.
link
sadgit 2878 days ago
But you still seem to be in agreement that the implementation of the language has a neccesary overhead... printing the operator that indicates code would require another escape sequence, and the overhead of the operator to identify code would mean that some compressible strings dont benefit from compression.
link
svantana 2878 days ago
Well of course -- any machine/language is a map from inputs (programs) to outputs, and the pigeon hole principle enforces that if some strings are shortened, others must be lengthened.
link