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

1

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.

  • 0
    Good point about half-information. Hmm, that makes my problem much less interesting than initially thought. ;-)2012-03-02
0

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

  • 0
    How are you defining *first digit*? The string is infinite in both directions.2012-03-02