News for hackers. Stuff that matters.
Re:9,73,241,561,1081,1849,_?_ by amichail on Thursday November 05, 2009 @12:37PM (#924243)
This question is not well-defined. Any number can be a solution.
Re:9,73,241,561,1081,1849,_?_ by bdr on Thursday November 05, 2009 @12:45PM (#924264)
Here's one interpretation: What will the simplest program that outputs these numbers output next?
Re:9,73,241,561,1081,1849,_?_ by amichail on Thursday November 05, 2009 @12:47PM (#924273)
How will you prove that your answer is correct?
Re:9,73,241,561,1081,1849,_?_ by bdr on Thursday November 05, 2009 @01:08PM (#924317)
Well, that could be done by brute force. Realistically, though, it's more about whether anyone can beat your answer.
Re:9,73,241,561,1081,1849,_?_ by jcl on Thursday November 05, 2009 @03:10PM (#924647)
I 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.

Re:9,73,241,561,1081,1849,_?_ by g__ on Thursday November 05, 2009 @04:46PM (#924852)
You'd have to determine if a program halts. Unless you restrict to non-Turing-complete language, this is undecidable.
Re:9,73,241,561,1081,1849,_?_ by jcl on Thursday November 05, 2009 @07:21PM (#925145)
You 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.
Re:9,73,241,561,1081,1849,_?_ by eru on Thursday November 05, 2009 @05:29PM (#924934)
I can decide if some programs halt. (Just not for all.)
Re:9,73,241,561,1081,1849,_?_ by duh on Thursday November 05, 2009 @01:33PM (#924392)
You can only prove that the answer is incorrect.
Re:9,73,241,561,1081,1849,_?_ by amichail on Thursday November 05, 2009 @01:45PM (#924429)
Why would you think that?
Re:9,73,241,561,1081,1849,_?_ by jey on Thursday November 05, 2009 @03:59PM (#924754)
It 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.
Re:9,73,241,561,1081,1849,_?_ by eru on Thursday November 05, 2009 @05:27PM (#924930)
It's only difficult in general. Nobody says there aren't any easy instances.
Re:9,73,241,561,1081,1849,_?_ by jey on Thursday November 05, 2009 @05:39PM (#924947)
Sure, 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?
Re:9,73,241,561,1081,1849,_?_ by eru on Thursday November 12, 2009 @11:08PM (#939342)
Look at primitive recursive functions.

E.g. see http://en.wikipedia.org/wiki/Primitive_recursive_function

Re:9,73,241,561,1081,1849,_?_ by jey on Friday November 13, 2009 @01:13PM (#940434)
Even 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.
Re:9,73,241,561,1081,1849,_?_ by eru on Friday November 27, 2009 @08:46PM (#964681)
That might be possible. Primitive recursion is much less powerful than Turing machines.
Re:9,73,241,561,1081,1849,_?_ by Leon on Thursday November 05, 2009 @01:01PM (#924298)
occam's razor
Re:9,73,241,561,1081,1849,_?_ by alain94040 on Thursday November 05, 2009 @03:25PM (#924686)
print "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?

Re:9,73,241,561,1081,1849,_?_ by jcl on Thursday November 05, 2009 @07:07PM (#925113)
Sorry, 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
Re:9,73,241,561,1081,1849,_?_ by tomstuart on Thursday November 05, 2009 @01:48PM (#924438)
The simplest program that outputs these numbers is the program that outputs these numbers, so it doesn't output anything next.
Re:9,73,241,561,1081,1849,_?_ by ivankirigin on Thursday November 05, 2009 @02:00PM (#924469)

  python -c 'print 9,73,241,561,1081,1849
  # or better yet
  echo 9,73,241,561,1081,1849
Re:9,73,241,561,1081,1849,_?_ by chaosprophet on Thursday November 05, 2009 @02:09PM (#924492)
You forgot the 'output next', bit of the question ;)
Re:9,73,241,561,1081,1849,_?_ by ivankirigin on Thursday November 05, 2009 @04:10PM (#924777)
You forgot to read the parent comment ;)
Re:9,73,241,561,1081,1849,_?_ by billpg on Thursday November 05, 2009 @01:49PM (#924446)
Define "simplest program"?
Re:9,73,241,561,1081,1849,_?_ by rsaarelm on Thursday November 05, 2009 @05:03PM (#924889)
The shortest program in a low-level language. On the definition of a low-level language, see: http://www.paul-almond.com/WhatIsALowLevelLanguage.htm
Re:9,73,241,561,1081,1849,_?_ by scott_s on Thursday November 05, 2009 @03:17PM (#924666)
Reasonable people understand that we're looking for a closed-form solution that can generate these numbers.
Re:9,73,241,561,1081,1849,_?_ by amichail on Thursday November 05, 2009 @03:24PM (#924684)
You 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)

Re:9,73,241,561,1081,1849,_?_ by scott_s on Thursday November 05, 2009 @03:55PM (#924746)
Luckily, mathematicians have already done this for me: 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."

Re:9,73,241,561,1081,1849,_?_ by amichail on Thursday November 05, 2009 @04:27PM (#924816)
Which 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?

Re:9,73,241,561,1081,1849,_?_ by scott_s on Thursday November 05, 2009 @04:40PM (#924841)
The explanation was clear what kind of functions are allowed: 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.)

Re:9,73,241,561,1081,1849,_?_ by amichail on Thursday November 05, 2009 @04:54PM (#924870)
There's no reason to not allow arbitrary programs.

Moreover, even if we agree to use a certain form of closed expression, you will still need to define how we measure the size of such an expression and you will need to find a way to prove that an answer has the smallest possible expression size.

Re:9,73,241,561,1081,1849,_?_ by scott_s on Thursday November 05, 2009 @05:08PM (#924899)
Sure there's a reason: someone said so.

I also said nothing about "smallest possible expression size."

Re:9,73,241,561,1081,1849,_?_ by edw519 on Thursday November 05, 2009 @01:46PM (#924432)
This 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.

Re:9,73,241,561,1081,1849,_?_ by viraptor on Thursday November 05, 2009 @06:32PM (#925065)
Is 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)