11 ms·
Here's one interpretation: What will the simplest program that outputs these numbers output next?
by bdr 17y ago
Here's one interpretation: What will the simplest program that outputs these numbers output next?
- amichail 17y agoHow will you prove that your answer is correct?
- Leon 17y agooccam's razor
- deleted 17y ago[deleted]
- bdr 17y agoWell, that could be done by brute force. Realistically, though, it's more about whether anyone can beat your answer.
- jcl 17y agoI don't know why you're being modded down. To elaborate: You can define "simplest program", for instance, as "shortest string consisting of [0-9], plus, minus, times, parentheses, and the symbol 'n' that when evaluated as a mathematical expression yields the given sequence for n=1, 2, 3...". You can then find a suitable string, like "((8 * n + 4) * n - 4) * n + 1", and do an exhaustive search of shorter strings to show that no better string exists. That would be 16^16, or less than a year on a computer that can knock off a trillion strings per second -- less if you use logic to constrain the search space. However, realistically, a person asking such a question is merely looking for a "good" solution, not necessarily a proven-optimal one, as there may be multiple reasonable explanations for a given sequence. Rather, the value of the "simplest program" criteria is that it allows you to compare proposed solutions. So, yes, for any given number, there is a formula to make it next in the sequence. But by applying the "simplest program" criteria, we see that some formulas -- and hence some values -- are better than others.
- g__ 17y agoYou'd have to determine if a program halts. Unless you restrict to non-Turing-complete language, this is undecidable.
- eru 17y agoI can decide if some programs halt. (Just not for all.)
- jcl 17y agoYou can simply modify your definition of "simplest" to be "shortest that completes in a million steps" or some such. A program that takes so long to finish that you're not sure it will return your desired value is probably not the simplest.
- duh 17y agoYou can only prove that the answer is incorrect.
- amichail 17y agoWhy would you think that?
- jey 17y agoIt only takes a counter-example (an example of a shorter program) to show that an answer is incorrect, but you could probably pick up a Turing Award or two if you find a way to put a tight bound on the Kolmogorov complexity of a bit string.
- eru 17y agoIt's only difficult in general. Nobody says there aren't any easy instances.
- jey 17y agoSure, there's a bunch of trivial/easy ones for programs that do almost nothing, but I really wonder if are there any interesting programs for which tight bounds are known?
- eru 17y agoLook at primitive recursive functions. E.g. see http://en.wikipedia.org/wiki/Primitive_recursive_function http://en.wikipedia.org/wiki/Primitive_recursive_function
- jey 17y agoEven if we limit it to primitive recursive functions, how can we put a bound on the Kolmogorov complexity of one? We'd need some way of coming up with bounds on the smallest Turing machine to compute that function.
- tomstuart 17y agoThe simplest program that outputs these numbers is the program that outputs these numbers, so it doesn't output anything next.
- ivankirigin 17y agopython -c 'print 9,73,241,561,1081,1849 # or better yet echo 9,73,241,561,1081,1849
- chaosprophet 17y agoYou forgot the 'output next', bit of the question ;)
- ivankirigin 17y agoYou forgot to read the parent comment ;)
- billpg 17y agoDefine "simplest program"?
- rsaarelm 17y agoThe shortest program in a low-level language. On the definition of a low-level language, see: http://www.paul-almond.com/WhatIsALowLevelLanguage.htm http://www.paul-almond.com/WhatIsALowLevelLanguage.htm
- alain94040 17y agoprint "9,73,241,561,1081,1849,0". So 0 is the answer. Actually, any digit, so I don't waste one extra character in my program. Did I win?
- deleted 17y ago[deleted]
- jcl 17y agoSorry, the APL program is only 26 characters: +/1 ¯4 4 8×[2](⍳9)∘.*¯1+⍳4 And outputs: 9 73 241 561 1081 1849 2913 4321 6121