4 ms·
Well, that could be done by brute force. Realistically, though, it's more about whether anyone can beat your answer.
by bdr 17y ago
Well, 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.