Is there a theorem that says that there is always more than one way to "continue a finite sequence"? - MathOverflow

Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2009-11-06T21:38:33Z

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.

Answer by HW for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2009-11-06T21:42:15Z

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.)

Answer by Qiaochu Yuan for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2009-11-06T21:42:36Z

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$.)

Answer by Jason Dyer for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2009-11-06T22:17:18Z

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

Given n terms , start with a polynomial of degree n:

Create a system of n equations such that for each polynomial where x = 0, .. , n-1 the polynomial is set equal to .

Solve the system of equations for all terms and voila, a formula.

Now repeat the same thing for a polynomial of one higher degree, dropping the term so there are still n terms in total.

Voila, a second formula.

Answer by Gabe Cunningham for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2009-11-06T22:32:53Z

Here's how I think about this. Suppose you're given n terms Define , where the denominator skips the factor . Consider the function f(x) = . Then for i an integer between 1 and 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.

Answer by S. Carnahan for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2009-11-06T22:47:14Z

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.

Answer by Kristal Cantwell for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2009-11-06T23:01:07Z

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]

Answer by fedja for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2009-11-07T05:10:02Z

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.

Answer by Jose Brox for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2009-11-07T08:07:31Z

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.

Answer by Nick S for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2011-01-23T00:28:39Z

(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...

Answer by Timothy Chow for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2011-09-12T21:36:17Z

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.

Answer by Vijay D for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2011-09-13T00:39:25Z

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.