2 ms·
How will you prove that your answer is correct?
by amichail 17y ago
How 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.