Re:Kolmogorov Complexity and Our Search for Meaning
by antidesitter on Friday August 03, 2018 @09:59PM
(#17684972)
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.
Re:Kolmogorov Complexity and Our Search for Meaning
by sadgit on Friday August 03, 2018 @09:45PM
(#17684928)
> 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?
Re:Kolmogorov Complexity and Our Search for Meaning
by nl on Friday August 03, 2018 @11:21PM
(#17685206)
No, you can conceive a language which echos everything unless it is prefixed with an operator indicator.
Re:Kolmogorov Complexity and Our Search for Meaning
by sadgit on Saturday August 04, 2018 @12:19AM
(#17685360)
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.
Re:Kolmogorov Complexity and Our Search for Meaning
by svantana on Saturday August 04, 2018 @06:06AM
(#17686207)
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.
Re:Kolmogorov Complexity and Our Search for Meaning
by enkid on Friday August 03, 2018 @09:14PM
(#17684853)
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.
Re:Kolmogorov Complexity and Our Search for Meaning
by smadge on Saturday August 04, 2018 @08:37AM
(#17686627)
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.
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.