7
$\begingroup$

I have come across a bit of folklore(?) which goes something like "given any finite sequence of numbers, there is more than one 'valid' way of continuing the sequence". For example see here. I would like to know if this is actually stated and proved rigorously, and if so, where can I find a statement and proof?

EDIT: The first couple of answers reflect my concerns exactly. But to quote from the book review I linked to,

Wittgenstein's Finite Rule Paradox implies that any finite sequence of numbers can be a continued in a variety of different ways - some natural, others unexpected and surprising but equally valid.

I didn't use the terms "Wittgenstein's Finite Rule Paradox" and "Wittgenstein on rule-following" before as googling them turns up results which look more like philosophy and linguistics than mathematics. My background in logic is nonexistent, I'm looking for any logicians out there who may have seen this before.

$\endgroup$
9
  • 4
    $\begingroup$ In response to your edit, this is philosophy and linguistics, not logic. What is natural or unexpected depends entirely on what kind of patterns you prefer. $\endgroup$ Nov 6, 2009 at 22:00
  • 17
    $\begingroup$ -1, this isn't mathematics, and we shouldn't feed the people who are inevitably (and have already) going to come and ask us "what's the next number in ..." $\endgroup$ Nov 7, 2009 at 6:08
  • 11
    $\begingroup$ I like the question and it led to 8 nice answers $\endgroup$
    – Gil Kalai
    Nov 27, 2009 at 18:31
  • 2
    $\begingroup$ @Scott: wait, wouldn't an affirmative answer to this question be more like starving people who come asking us to continue a sequence? $\endgroup$
    – aorq
    Jan 28, 2010 at 16:31
  • 3
    $\begingroup$ @Charles Roque: Scott posted his comment when this question was rather stupidly named "Continuing a finite sequence." I just changed it to the current title today. Orthogonally, it's interesting how a title-change translates into interest in a question terms of views and votes. (I got 3 upvotes within a couple of hours.) $\endgroup$ Jan 28, 2010 at 18:06

11 Answers 11

29
$\begingroup$

Since you mentioned Wittgenstein's paradox, I thought someone should explain what that is. Warning: As you suspected, what follows is really philosophy and not mathematics. Nevertheless, it seems worth clarifying what people mean by Wittgenstein's paradox so that you don't go chasing wild geese.

In Wittgenstein's Philosophical Investigations, he makes an argument about "private languages" that Saul Kripke later interpreted in a certain way. The basic point is that it is very difficult, if not impossible, to pin down what a "rule" is. Imagine that you are trying to teach a Martian the syntactic rule, "append a 1 to the end of a string." The Martian looks puzzled so you give some examples:

0 $\to$ 01
101 $\to$ 1011
0010 $\to$ 00101

and so forth. The Martian seems to get the idea, and does a few examples to confirm with you. The first few examples look good, but then all of a sudden the Martian comes up with

1111111 $\to$ 111111110

Say what? Somehow it seems that the Martian hasn't gotten the rule after all. Or maybe the Martian has extrapolated from your examples to a different rule? How do you make sure you communicate the rule you intend? If you have previously already agreed on some basic rules then you can build on those to define new rules, but how do you get started? It's hard to get more basic than "append a 1."

Perhaps you could try building a physical device that optically scans its input and writes a 1 next to it. But any physical device will eventually fail to implement your intended "append a 1" rule when it reaches a certain physical limit, so the device doesn't unambiguously communicate your intended rule to the Martian either.

No matter how you slice it, it seems that you can't guarantee that you have communicated your rule to the Martian, since any finite amount of interaction is consistent with infinitely many rules. Once we see this, we could take a more radical step and wonder, maybe I'm the Martian. Maybe all these years I've been assuming that I know what people mean when they specify syntactic rules, but actually I've just been lucky and haven't discovered the discrepancy between my understanding of what "append a 1" means and what everyone else means by it. (Here you can get a glimpse of where Wittgenstein's term "private language" comes into the discussion.) Even more radically, we could wonder whether the notion of a "rule" is incoherent. Perhaps there really is no such thing as a "rule" in the sense of some unambiguous finite description of something that applies to an infinite number of cases.

Anyway, it is not my intent to start a debate here on MO about this issue, about which many philosophical papers have been written. It is just to confirm that Wittgenstein isn't who you're looking for, if you want a mathematical answer to your question.

$\endgroup$
21
$\begingroup$

As others have mentioned, there can be many ways to continue a sequence, but it can be difficult to argue that a particular way is best. Kolmogorov complexity gives us a quantitative method to say that one way to continue a sequence is better than another. Namely, the "better" method is the one that can be specified with a smaller ruleset. However, this does not necessarily yield a unique answer, and your answer can depend on the language you use to specify your rules.

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 6, 2009 at 23:07
  • 1
    $\begingroup$ 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". $\endgroup$ Nov 24, 2010 at 14:20
  • $\begingroup$ @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. $\endgroup$ Sep 13, 2011 at 1:06
  • $\begingroup$ @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. $\endgroup$
    – S. Carnahan
    Sep 13, 2011 at 5:12
  • $\begingroup$ @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) $\endgroup$ Sep 13, 2011 at 14:11
15
$\begingroup$

That depends entirely on your definition of "valid." If "valid" means "describable by a Turing machine," then the answer is trivially yes. For example, here are three:

  • The unique interpolating polynomial of minimal degree.
  • The periodic sequence given by repeating what was given.
  • The sequence which is constant after what was given.

Edit: Sequence-continuation problems happen to be one of my pet peeves. I do not consider them mathematical exercises, but psychological and cultural: the real goal of any sequence-continuation exercise is to understand what kind of sequences would interest the person who came up with the exercise and what they would consider meaningful. And that is not mathematics.

My favorite example of this is the following sequence: $1, 1, \infty, 5, 6, 3, ...$. How does it continue? (I won't spoil the answer; try looking it up on the OEIS if you're stuck. They write $\infty$ as $-1$.)

$\endgroup$
7
  • 7
    $\begingroup$ People who say that sequence-continuation problems are one of their pet peeves are one of my pet peeves. $\endgroup$ Nov 6, 2009 at 21:59
  • 1
    $\begingroup$ "Sequence-continuation problems happen to be one of my pet peeves." I totally agree! Psychologically, the reason I'm asking this question is that I want to see a 'proof' that sequence-continuation is not a mathematical exercise. $\endgroup$ Nov 6, 2009 at 22:01
  • $\begingroup$ What would you consider a "proof"? $\endgroup$ Nov 6, 2009 at 22:06
  • 1
    $\begingroup$ And all this time I've been trying to figure out what to feed my peeves... $\endgroup$
    – GS
    Jan 28, 2010 at 13:55
  • 4
    $\begingroup$ Just so I can make my point better, the sequence I gave above is the number of regular polytopes in n dimensions (starting from zero). I cannot imagine any conceivable problem-solving method that could have deduced this from the sequence alone unless you were already familiar with it. $\endgroup$ Jan 28, 2010 at 14:01
7
$\begingroup$

There is an area of computer science called grammatical inference.

Let $\Sigma$ be a finite alphabet, $\Sigma^*$ be the set of finite length strings over $\Sigma$ and a language be a set of strings. Let $F$ be a family of languages. The data for the problem is a sequence of words $w_0, w_1, \ldots$ from a language in $F$. A learner receives the data and generates a sequence of languages $H_0, H_1, \ldots$ called hypotheses.

Typically the hypothesis $H_i$ includes all words provided till that point. The learner stabilizes if the hypotheses do not change after a point and is successful if the stable hypothesis is the language from which the words were drawn. A family of languages can be learnt in the limit if there is an algorithm that can successfully learn the source language.

There is a theorem due to E. Mark Gold (Language Identification in the Limit, 1967) stating that if the family $F$ contains all languages of finite cardinality and at least one language of infinite cardinality, it cannot be learnt in the limit.

This result may be one formalisation related to the original question, but does not tell the whole story. Dana Angluin (Inference of Reversible Languages, 1982) showed that there are families containing infinitely many languages that can be learnt in the limit. There is a recent text Grammatical Inference: Learning Automata and Grammars by Colin de la Higuera devoted to this area.

$\endgroup$
4
$\begingroup$

It depends on the context in which the sequence is viewed. If some sort of meaningful information is compressed the better the compression the more the digits representing the compressed information resemble a random number and the more the remainder of the sequence is unpredictable and hence has more possible continuations. In some mathematical contexts a random number is desired predictability is bad for a random number. So again in this case there would be many valid continuations. In the case of a random number you do not want low Kolmogorov complexity. There are problems in which randomness helps see the section entitled "When randomness helps" at the wiki article at:

[http://en.wikipedia.org/wiki/Randomized_algorithm]

$\endgroup$
4
$\begingroup$

I believe you mean "describable by a polynomial formula", in which case the answer is "yes".

Given $n$ terms $s_0, \cdots, s_{n-1}$, start with a polynomial of degree $n$:

$$a_1x^n+a_2x^{n-1}+ \cdots + a_{n-1}x + a_n$$

Create a system of $n$ equations such that for each polynomial where $x = 0, \ldots , n-1$ the polynomial is set equal to $s_0, \cdots, s_{n-1}$.

Solve the system of equations for all terms $a_1, \cdots, a_n$ and voila, a formula.

Now repeat the same thing for a polynomial of one higher degree, dropping the $a_{n-1}x$ term so there are still $n$ terms in total.

Voila, a second formula.

$\endgroup$
1
  • $\begingroup$ Nice characterisation of a similar point here: qntm.org/1111 $\endgroup$
    – Seamus
    Mar 21, 2010 at 17:59
3
$\begingroup$

Normally, "valid" means "defined by a clear and short rule". Formally we may talk about having a generating program on some abstract machine that is much shorter than the sequence itself. The formal unique continuation statement would be "for each $n$ there is $m$ such that if two infinite sequences generated by valid programs of length $n$ coincide in the first $m$ positions, they coincide in all positions. That is trivially true because there are only finitely many programs of length $n$ but the real mathematical question is whether there is any way to effectively estimate $m$ given $n$? My knowledge of logic is too shaky to answer that but, I hope, somebody more knowledgeable will enlighten us.

$\endgroup$
2
$\begingroup$

Here's how I think about this. Suppose you're given $n$ terms $a_1,\dots, a_n$. Define $b_i = a_i / (i-1)\cdots(i-n)$, where the denominator skips the factor $(i-i)$. Consider the function

$$f(x) = b_1(x-2)(x-3)\cdots(x-n) + (x-1)b_2(x-3)\cdots(x-n) + \cdots + (x-1)\cdots(x-n+1)b_n + (x-1)\cdots(x-n)c$$

Then for $i$ an integer between $1$ and $n$, $f(i) = b_i \ast (i-1) \ast \cdots \ast (i-n)$, except that you skip the factor $(i-i)$. Thus, $f(i) = a_i$. But by changing $c$, you can make the next term $f(n+1)$ whatever you want.

$\endgroup$
1
1
$\begingroup$

Sonia, you need to define what you mean by "valid". Otherwise, I can continue in any way I want. For instance, here are two different continuations of the sequence "3,1,4,1":

3,1,4,1,0,0,0,0,0,0,0,0...

3,1,4,1,1,1,1,1,1,1,1,1...

(There's also a more famous way of continuing this sequence.)

$\endgroup$
1
  • 4
    $\begingroup$ 3.1.4.99999999999999999999999999999999999999999999999? $\endgroup$ Jan 28, 2010 at 14:38
1
$\begingroup$

There is no "a priori" valid way of continuing a sequence... there are many of them! (In fact, uncountable infinitely many).

Think of the first terms of your sequence as the integer part of a real number; for example, if you start with $\{2,4,6,8\}$ think you have the number $2468,...$. In how many ways can you continue this real number by its decimal part?

You see that we have $2468,0000...$ and $2468,1000...$, and $2468,01000...$, and $2468,101001000...$ and... that is, we can take any real number in the interval $\[2468,2469\]$. But for any of these reals we have an obvious way to continue your sequence, namely by taking every next decimal as the next element of the sequence (e.g., $2468,10111213...$ gives $\{2,4,6,8,1,0,1,1,1,2,1,3,...\}$.

Thus, there are at least as many ways of continuing your sequence as there are real numbers in $\[2468,2469\]$, i. e., uncountably many.

(Note that for every of these reals, we could also take every TWO (or three, or four...) decimals as the next element of the sequence, or even take an arbitrary number of decimals for every new element; whence there are in fact "more" ways to continue the sequence than real numbers in that interval).

You would have a different case if you had a good criterion for determining "a posteriori" which sequence continuations are accepted as 'natural' and which ones not; but then, the number of 'valid' continuations will completely depend on that criterion (and should be computed in every case), and not in any axiom or theorem of general mathematics.

$\endgroup$
0
$\begingroup$

(Most of the things I post have already been covered in the previous answers, but not combined this way).

Here is my view of the problem:

Given a finite sequence of numbers $a_1,...,a_n$ we can use the Lagrange interpolation formula to get a polynomial $P(x)$ so that $a_k=P(k) \forall k \leq n$.

As yuan mentions this is an unique answer in the following two (equivalent) ways: - The only polynomial of degree at most $n-1$ which fits this data - The polynomial of smallest degree which fits this data.

Now pick a function $f : R \rightarrow R$ {\bf at random}. Let $g(x)= P(x)+ (x-1)(x-2)...(x-n)f(x)$.

Then $g(1)=a_, ..., g(n)=a_n$, and this provides uncountably many different ways of continuing $a_1,...,a_n$.


Second point:

Pick an $x$ at random. Isn't then any "natural" way of continuing the sequence $a_1,...,a_n, a_{n+1}=x$ also in some sense a "natural" way of continuing $a_1,...,a_n$?

But each choice of $x \in R$ leads to a different answer...

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.