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](http://www.guardian.co.uk/books/2005/feb/05/featuresreviews.guardianreview13). 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.



Is there a theorem that says that there is always more than one way to "continue a finite sequence"?
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.


