3
$\begingroup$

π is palindromic

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$?

  • 4
    I don't understand how an infinite sequence can be said to be palindromic.2012-03-02
  • 0
    @GerryMyerson It’s the same read backwards as read forwards. Look at my definition of $P$. This is actually a pretty common kind of grammar, used for instance to search for biological motives in computational genomics.2012-03-02
  • 2
    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?2012-03-02
  • 3
    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.2012-03-02
  • 1
    @Gerry I don’t know your prior knowledge in the field of formal languages so it’s hard to give an appropriate answer. But reading an infinite sequence backwards *is* well-defined (note that the same isn’t true in general for infinite *numbers*). Again, look at my definition of $P$. This is how you can read and write an infinite palindromic sequence. Imagine it like having an infinite piece of string of which you hold both ends in your hands, but they connect somewhere infinitely far away.2012-03-02
  • 0
    $\ldots 11111 \ldots$ is "trivially" palindromic.2012-03-02
  • 2
    @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.2012-03-02
  • 0
    @davin Perhaps this is just my question: is my palindrom-generating pattern fundamentally different from any other infinite sequence that represents a number (such as $\pi$ or $1.\overline1$? Does it make sense to generate numbers using this rule, and can we calculate with them? I’m not sure what you mean by “I don’t see the meaning” since I’m *giving* it a meaning (or rather, asking whether this is consistently possible).2012-03-02
  • 1
    @davin,@Gerry: A bi-infinite word over an alphabet $A$ is a function $w:\mathbb{Z}\to A$. There are several natural ways to define *palindrome* for such words. At the least one would probably want to include both those words with the property that $w_n=w_{-n}$ for all $n$ and those for which $w_n=w_{1-n}$ for all $n$; if one doesn’t care about the location of the origin, one could also include shifts of these words.2012-03-02
  • 2
    @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\}$.2012-03-02
  • 0
    It’s easy to define operations on such sequences, even fairly natural ones, that allow one to do calculations in the broad sense of the word, so you need to be more precise: in what sense do you mean *calculations*? If you want this system to extend or in some sense mesh nicely with ordinary arithmetic of real numbers, I suspect that you’re out of luck.2012-03-02
  • 0
    @Brian That’s why I gave the two examples. For instance, how would you define the result of multiplication consistently so that (e.g.) $10k$ yields a consistent result or that you could solve for roots of quadratic equations. Generally, how would you define a consistent set of arithmetic operations for it? Does such a system exist? I lack the proper terminology to even describe what kind of answer I want, but the first question would be if such terminology actually exists.2012-03-02
  • 0
    You insist on referring to these objects as *sequences*. They may be perfectly well-defined and fascinating objects of mathematical study, but one thing they are **not** is sequences.2012-03-03
  • 0
    @Gerry Ah yes, you are of course absolutely right.2012-03-05

2 Answers 2