6 ms·
This question is not well-defined. Any number can be a solution.
by amichail 17y ago
This question is not well-defined. Any number can be a solution.
- bdr 17y agoHere'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
- edw519 17y agoThis question is not well-defined. It's defined just well enough to identify you as someone who'd rather debate the problem than attack it. In other words, it has done its job.
- viraptor 17y agoIs it defined well enough to allow you to draw that kind of conclusions without any context? What if that question was meant to find people who think about what is the real goal and asking "are we thinking about the same thing, or should we agree on more details" instead of attacking the problem at hand. Otherwise "0" is a perfectly good answer (for any reason). This discussion has as much sense as a typical IQ test... (~nil)
- scott_s 17y agoReasonable people understand that we're looking for a closed-form solution that can generate these numbers.
- amichail 17y agoYou would still need to define precisely what you mean by a closed-form solution and this definition needs to be part of the question. But even then you would be faced with the difficult task of proving that your answer is correct. This kind of ill-defined question might be a fun diversion but it should never be used for any serious purpose (e.g. in any test/assighnment that matters)
- scott_s 17y agoLuckily, mathematicians have already done this for me: http://en.wikipedia.org/wiki/Closed-form_solution http://en.wikipedia.org/wiki/Closed-form_solution Note, that I said "reasonable people." Reasonable people know what is being asked. If, for example, I asked someone how much they weigh, they are not going to respond "I don't know. I weighed myself five minutes ago, but I must have a different weight right now."
- amichail 17y agoWhich functions do you allow in closed-form solutions? Do you allow Turing-completeness? If not, why not? What exactly is the measure used to determine the size of a solution?
- scott_s 17y agoThe explanation was clear what kind of functions are allowed: http://en.wikipedia.org/wiki/Elementary_function_%28differential_algebra%29 http://en.wikipedia.org/wiki/Elementary_function_%28differen... Again, reasonable people. If we had to precisely define every question and interaction, we would never get anything done. Instead we rely on shared assumptions and clarify only when actual confusion occurs. (Yours is not an actual confusion.)