ChapterZero

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 where , let . is well-defined, assuming a unique decimal expansion for every positive integer. Let the sequence ; then T has the property that is in only in case is a finite sequence of positive integers.