# Infinite palindromic numbers Today’s Abstruse Goose comic got me thinking:

Does an “infinite palindromic” number (other than the obvious $x\times1.\overline1$) make sense?

In any conventional number system, the answer (as far as I know) is “no”. But on the other hand, I can trivially construct a context free grammar to generate such a sequence:

\begin{align} \color{gray}{P} \rightarrow& 0\ \color{gray}{P}\ 0 \\\\ |\ & 1\ \color{gray}{P}\ 1 \end{align}

This generates an infinite palindromic sequence of $0$s and $1$s. My question: is there a number system which allows me to do calculations with such a sequence?

That is, have we got a number system which tells me the result of $k + k$, $k = 101{…}101$ (sounds simple: $202{…}202$ … but what about $10 \times k$?) or that can solve equations such as $x^2 = k$?

• I don't understand how an infinite sequence can be said to be palindromic. – Gerry Myerson Mar 2 '12 at 11:22
• How do you read an infinite sequence "backwards"? How is this any different from "the last several digits of pi"? An infinite sequence of zeros and ones is, by definition, a function from $\{{1,2,3,\dots\}}$ to $\{{0,1\}}$. How do you read it backwards? – Gerry Myerson Mar 2 '12 at 11:31
• It makes sense if it's of order type $\omega + \omega^*$ or $\omega^* + \omega = \zeta$. The latter is actually more interesting, since it's not immediately clear what the "center" is, and whether there might be more than one. – Yuval Filmus Mar 2 '12 at 11:37
• @KonradRudolph, your CFG isn't a good example, since it is merely a generating pattern for an infinite number of finite strings, so while the string length is indeed unbounded, every string belonging to the CFG/CFL is finite (since membership requires the absence of non-terminal characters). I too agree with Gerry's sentiment and can't see much meaning in an infinite palindrome. – davin Mar 2 '12 at 13:01
• @davin: Clearly Konrad’s grammar is to be interpreted as generating bi-infinite words. In fact it generates all such words over $\{0,1\}$ that can be indexed by $\mathbb{Z}$ in such a way that $w_n=w_{1-n}$ for all $n$. It does not generate the ‘odd’ palindromes over $\{0,1\}$. – Brian M. Scott Mar 2 '12 at 13:32

Interesting question - just some thoughts:

I'd guess it's impossible to speak of a usual infinite sequence $(w_0, w_1, \ldots)$ as being palindromic. That's because knowledge of the first character would - by definition - imply knowing the value of some "last" character, which is a problem: There is usually no definite last character to speak of, as the sequence continues infinitely. Tell me a last char and I go further in the sequence and tell you a different one.

Take ABABABAB.... Is this palindromic or not? Whenever the last character was an A, it surely is, with a B, it isn't. Now which one to take? It's feels to me kind of like asking what is $\lim_{x \to \infty} \sin x$.

The only case where it would make sense to speak of knowing the last char of a sequence is when it was constant from some point on. But in order to be palindromic, that means that our sequence has to be constant at all, because again, if it changed in the front, it would have to change at the end as well and thus wouldn't be constant from some point -> Contradiction. (Or simply because the beginning resembles the end!).

Your grammar example is even more tricky, because it doesn't even generate a well-defined infinite sequence, that is, converge to some function $w : \mathbb N \to \{0,1\}$. It produces partial, finite strings, but in the infinite case, the definition is meaningless. Every production step taken may change the whole sequence - except we'd always use either $0$ or $1$ - and thus the result is again constant.

Now what you might want to use is not an indexing $w : \mathbb N \to \{0, 1\}$ but a bi-infinite sequence $w : \mathbb Z \to \{0, 1\}$ such that e.g. $w(-z) = w(z)$ for all $z \in \mathbb Z$. Such a thing could rightfully be called palindromic. However remember that a palindrome only contains half information, the second half is irrelevant as it's just a copy. You may have p-adic numbers encoded in the forward half, perform usual operations with them, reverse and built your new palindrome. In such a way you could have operations defined, though I see little use in it.

• Good point about half-information. Hmm, that makes my problem much less interesting than initially thought. ;-) – Konrad Rudolph Mar 2 '12 at 16:58

$nk$ could start with the first digit of $n \ \times$ the first digit of $k$.
The first $m$ digits of $\sqrt k$ could be obtained by writing the first $2m$ digits as an integer and square rooting that, but I can't think of any way to define the last digit. $k+j$, where $k$ and $j$ are both infinite, could mean adding the first digits of $k$ to the first digits of $j$, and the last digits of $k$ to the last digits of $j$, whereas if $j$ is finite then $j$ would be added only to the last digits of $k$. This would mean that $10k+k=2k$ rather than $11k$, which would be interesting...

• How are you defining first digit? The string is infinite in both directions. – Brian M. Scott Mar 2 '12 at 13:34