News for hackers. Stuff that matters.
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