ChapterZero

The sequence of all finite sequences

Filed under: Mathematics — Alex @ 11:47 am 7/18/2005

An interesting question arose today– posed by a student– in the Hilbert space class. Can you construct a sequence of sequences, such that this sequence contains every finite sequence of positive integers as a term? I would guess that the sequence wouldn’t contain any other terms.

Ordinarily a problem like this would give me an hour of pleasurable cogitation :), but I’ve seen the answer to this before, in Dick Grune’s Parsing book. In fact, it seems like the author of the question, a senior comp. sci. major, has probably seen a proof of this in one of his automata classes, and forgot it.

Given a finite sequence $\{a_n\}_{n \in \Z_j}$ where $\Z_j = \{1, 2, \ldots, j\}$ , let $f(\{a_n\}) = \sum_{i=1}^j 10^{a_n}$ . $f^{-1}$ is well-defined, assuming a unique decimal expansion for every positive integer. Let the sequence $T = \{t_i = f^{-1}(i) \}$ ; then T has the property that is in only in case is a finite sequence of positive integers.