Irrational numbers generated by a deterministic cellular automaton?

Question

If we consider a simple 1D cellular automaton (acting on a binary string) and record a value at a fixed position in the string, we can interpret the recorded sequence as a binary number.

Most simple deterministic cellular automata generate periodic sequences of binary digits which can be interpreted as rational numbers.

However, there are 'random' deterministic CA, such as elementary CA rule 30, discovered by S. Wolfram. Starting from a single point, it generates data which is random enough to be used as a random number generator. See this paper for more information.

Now, since this CA has perfectly deterministic (and simple) rules, what can we tell about numbers it generates at fixed string positions?

Since most of the 'randomness' happens to the right side, let's look at the numbers we get at positions from the center to the right, starting from the topmost $1$ in each case (see the figure). All the numbers are considered to have zero integer parts and are converted to the decimal notation from binary:

$$a_0=0.8623897839473840486408002460867511281\dots$$

$$a_1=0.6619938131535679545367590611375473724\dots$$

$$a_2=0.7759963493462055882598583123808285092\dots$$

$$a_3=0.7313593429560050953478343145780694591\dots$$

$$a_4=0.8215879687059052475349289186091204860\dots$$

$$a_5=0.6314259431664999548181068438831291123\dots$$

$$a_6=0.8079966728503828647993510584534608703\dots$$

Can we prove/disprove that these numbers are irrational? Trancendental? Or can we only guess based on direct experiments? What about other such 'random' cellular automata?

Answer 1

The answer itself isn't very surprising or illuminating so sorry :/

First, since you've posted a picture of rule 30, discussed here, we will be considering number generation from that CA only.

Second, recall the definition of an irrational number,

An irrational number is a number that cannot be expressed as a fraction p/q for any integers p and q.

Corollary 1:

Irrational numbers have decimal expansions that neither terminate nor become periodic.

Proof: Assume that the decimal expansion does repeat. Then the number is, by definition, rational. Thus, our assumption is false, and the corollary is true.

Now it's been proven by Jen 1990 that with the initial state of a single black cell, the sequence of colors attained in any two adjacent cells is not periodic. Corroborated by Gray 2003.

So if we define a sequence of numbers using the cell states generated by rule 30, then the digits will not be periodic. By Corollary 1, If the digits are not periodic, then the number is irrational.

So let's look at your question(s)

Can we prove/disprove that these numbers are irrational?

We can prove that these numbers are irrational, for rule 30.

Trancendental?

Almost surely.

What about other such 'random' cellular automata?

Any cellular automata with non-periodic evolution will also generate irrational numbers.

Answer 2

While almost all real numbers are transcendental, it is devilishly difficult to prove it for specific real numbers, especially those given by their base $b$ expansion. (For those "natural" quantities for which a proof of transcendence is known, it is generally by viewing these quantities as particular values of special functions and using techniques from analysis on such functions.) Unlike irrationality (a number is irrational iff its base $b$ expansion is not eventually periodic), there is nothing analogous for transcendence.

Even for the very simple-looking Champernowne constant ($0.12345678910111213...$), it was difficult to prove its transcendence. You shouldn't expect a proof of transcendence of quantities whose base $b$ expansions are defined by cellular automata.

There is, however, a remarkable result that bears at least some resemblance to what you're asking for, at least in the sense that the keywords "automaton", "base $b$ expansion" and "transcendence" appear in it:

If $x$ is a real number (and $b\geq 2$ an integer) such that the base $b$ expansion of $x$ is not eventually periodic, and "$b$-automatic" in the sense that the $i$-th decimal of $x$ in base $b$ can be computed by a finite automaton from the base $b$ expansion of $i$ itself, then $x$ is transcendental.

A first "proof" appeared as: Loxton & van der Poorten, “Arithmetic properties of automata: regular sequences”, J. Reine Angew. Math. 392 (1988), 57–69; however, that paper contains a flaw. A correct proof, together with related results and conjectured, appeared much more recently: Adamczewski & Bugeaud, “On the complexity of algebraic numbers I. Expansions in integer bases”, Ann. of Math. 165 (2007), 547–565. (Here is a survey related to such questions, although it does not seem to be aware that the Loxton & van der Poorten paper is flawed.)

This result implies, for example, that the number whose binary expansion is the Morse-Thue sequence, viz., $0.01101001100101101001...$, is transcendental (because it is certainly automatic and non periodic). This is certainly the closest you will get to the sort of quantities you were asking about.

(Also remarkably, for formal power series over finite fields, there is a result due to Christol, Kamae, Mendès-France and Rauzy which says essentially the "opposite" of the one quoted above: the coefficients of the formal power series are automatic iff the power series is algebraic.)