4 ms·
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
by jeromebaek 8y ago
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.
- enkid 8y agoArbitrary 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.
- smadge 8y agoArbitrary, 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.
- 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.
- antidesitter 8y agoWell, 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 https://arxiv.org/abs/math/0504351.
- akvadrako 8y agoThe shortest program that outputs "0" is "" (the null program) in the appropriate language, one that just outputs zero.