Hacker News Reader

Comment by jeromebaek | Hacker News Reader

Well, obviously, the shortest program that outputs "0" is "0". And the shortest program that outputs "1" is "1". We're only interested in the general case, not specific cases.

Sometimes I think this distinction between "general" and "specific" is as deep as the whole idea of uncomputability. When someone says "arbitrary Turing machine" it is very difficult for a layman to wrap their head around what this means. No wonder: I'm using the word "arbitrary", which means "random", which means... uncomputable.

View on HN

Well, obviously, the shortest program that outputs "0" is "0". And the shortest program that outputs "1" is "1". We're only interested in the general case, not specific cases.

Just wanted to note that we have techniques for termination analysis that cover entire classes of programs of arbitrary length, not just specific short programs. See ranking function synthesis for an example. Hell, under some universal computational models, the halting problem is polynomial-time decidable for almost all programs: https://arxiv.org/abs/math/0504351.

> 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?

No, you can conceive a language which echos everything unless it is prefixed with an operator indicator.

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.

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.

Arbitrary doesn't mean random. It means chosen randomly, as in any Turing Machine chosen randomly will work in that situation. The output isn't random, the output for one Turing Machine should be the same for all Turing Machines.

Arbitrary, when used in mathematics, also does not mean chosen randomly. It is used as a synonym for “any” or “every.” Furthermore, it doesn’t really make sense to speak of “choosing randomly” from a set without specifying a probability distribution. Often times it is implicit that someone is talking about a uniform distribution, but since the set of all Turin machines is infinite, it can’t have a uniform distribution.

The shortest program that outputs "0" is "" (the null program) in the appropriate language, one that just outputs zero.

Reply on news.ycombinator.com