Timeline for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 13, 2011 at 14:59 | comment | added | S. Carnahan♦ | I see. I suppose if I were left to my own devices, I would ask for the smallest number of states for a Turing machine that provably moves to the right (eventually) and outputs the chosen sequence of numbers (under some agreed-upon coding rule, like strings of 1s separated by single 0s). | |
| Sep 13, 2011 at 14:20 | comment | added | Timothy Chow | So can we pin down what "reasonable" means, and thereby actually solve specific finite extrapolation problems? Friedman picks a specific language that he thinks is reasonable, and as a first exercise, asks if its predictions for certain specific sequences coincide with our intuitions. If they do, then we can try other "reasonable" languages and see if they give the same answers. Of course we still expect no canonical answer to "pathological" finite extrapolation problems, but if the theory works for all "normal" examples then we've achieved something that Kolmogorov complexity theory has not. | |
| Sep 13, 2011 at 14:11 | comment | added | Timothy Chow | @S. Carnahan: Friedman picks one language to start with, but aims to show later that the resulting concept of simplicity is robust to "reasonable" changes in the choice of language. In the Kolmogorov complexity literature, people generally prove uniqueness up to some unspecified constant c, and they make no effort to investigate c further since it disappears asymptotically. So, e.g., languages containing arbitrarily large but finite lookup tables are allowed. But intuitively, those languages are "unreasonable." (continued) | |
| Sep 13, 2011 at 5:12 | comment | added | S. Carnahan♦ | @Timothy: Thank you for letting me know. However, from the first link, it looks like Friedman is avoiding the non-canonical choice of language by choosing a language once and for all. I don't understand some of the vocabulary well enough to tell if my interpretation is correct, though. | |
| Sep 13, 2011 at 1:06 | comment | added | Timothy Chow | @S. Carnahan: Harvey Friedman has made an attempt to get around the problem that you mention, of the non-canonical choice of language. See cs.nyu.edu/pipermail/fom/2004-January/007798.html and for a clarification of how his proposal differs from Kolmogorov complexity, see cs.nyu.edu/pipermail/fom/2004-January/007805.html Friedman's idea looks promising to me, but it's very sketchy, and I don't think he has developed it further. | |
| Jan 28, 2011 at 1:12 | vote | accept | Sonia Balagopalan | ||
| Sep 13, 2011 at 19:51 | |||||
| Nov 24, 2010 at 14:20 | comment | added | Martin Rubey | I think it is not a real problem that the program doing the "right" thing may be longer than one doing the silly thing: in this case the number of given terms is to small. Thus, one could ask for a program that is shorter than the one that simply lists the terms given and continues with zero. As an aside, Section 2.4 of an article by Kauers and Bostan, arxiv.org/abs/0811.2899 lists some ways to "check" whether a guessed formula is "correct". | |
| Nov 6, 2009 at 23:07 | comment | added | Ilya Nikokoshev | Also, for sequences with any non-trivial algorithm, like counting trees, the program that just prints the first 10 sequence numbers and then repeats will be in most languages shorter than the honest realization of algorithm. | |
| Nov 6, 2009 at 22:47 | history | answered | S. Carnahan♦ | CC BY-SA 2.5 |