3 ms·
> 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
by sadgit 8y 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?
- nl 8y agoNo, you can conceive a language which echos everything unless it is prefixed with an operator indicator.
- sadgit 8y agoBut 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.
- svantana 8y agoWell 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.