# Not all numbers are computable

Standard

When we hear the word number, symbols like 1,$\sqrt{2}$,¼, π (area enclosed by a unit circle), ι (symbol for $\sqrt{-1}$), ε (infinitesimal),  ω (ordinal infinity), ℵ (cardinal infinity), …. appear in our mind.  But not all numbers are  computable:

A computable number [is] one for which there is a Turing machine which, given n on its initial tape, terminates with the nth digit of that number [encoded on its tape].

In other words, a real number is called computable if there is an algorithm which, given n, returns the first n digits of the number. This is equivalent to the existence of a program that enumerates the digits of the real number. For example, π is a computable number (why? see here).

Using Cantor’s diagonal argument on a list of all computable numbers, we get a non-computable number (here is the discussion). For example, a sum of series of real numbers called Chaitin’s constant, denoted by Ω, is a non-computable number (why? see here).

Fun fact: We don’t know whether π is a normal number or not (though we want it to be a normal number), but Ω is known to be a normal number (just like the Mahler’s Number discussed here).

# Solution to the decimal problem

Standard

In this post I will discuss the solution of the problem I posted a week ago. Firstly I would thank Prof. Purusottam Rath for pointing out that this problem has already been solved. In 1961, Kurt Mahler published the solution in Lectures on Diophantine Approximations. In fact, $M=0.12345678....$ is called Mahler’s number since Mahler  showed it to be transcendental. For complete proof refer, Section 1.6 of “Making transcendence transparent: an intuitive approach to classical transcendental number theory“, by Edward Burger and Robert Tubbs, Springer-Verlag (2004). But I can give an outline of proof here.

The most basic type of transcendental numbers are the Liouville’s Numbers, these numbers satisfy following theorem (proved here on pp. 19):

Liouville’s Theorem: Let $\alpha$ be a real number . Suppose there exists an infinite sequence of rational numbers $p_n/q_n$ satisfying the inequality $\displaystyle{\left|\alpha - \frac{p_n}{q_n}\right|<\frac{1}{q_n^n}}$. Then $\alpha$ is transcendental.

To be able to apply this theorem we use truncation procedure i.e. obtain the approximations of the number $\alpha$  by truncating the decimal expansion of $\alpha$ immediately before each long run of zeros, and using this to get the desired inequality.

For Mahler number, Liouville’s theorem alone is not sufficient. Since, if we attempt truncation procedure, we will see that the number of decimal digits before each run of zeros far exceeds the length of the run. For example, a run of 2 zeros occurs after 189 digits. But, using Liouville’s theorem we can prove a partial result:

(1) There exists an infinite sequence of rational numbers $p_n/q_n$ satisfying the inequality $\displaystyle{\left|M - \frac{p_n}{q_n}\right|<\frac{1}{q_n^{4.5}}}$. Hence, Mahler number $M$ is either a transcendental number or an algebraic number of degree at least 5.

Since we need a stronger inequality, we will use following theorem (proved here on pp. 54), which states that:

Thue-Seigel-Roth Theorem: Let $\alpha$ be an irrational algebraic number. Then for any $\varepsilon > 0$ there exists a constant $c(\alpha, \varepsilon)$ depending on $\alpha$  such that $\displaystyle{\frac{c(\alpha,\varepsilon)}{q^{2+\varepsilon}}<\left|\alpha - \frac{p}{q}\right|}$

From this theorem we conclude that

(2) If $M$ is algebraic of degree $d\geq 2$ (I showed in previous post that it is irrational) then for $\varepsilon =0.5$ there exists a constant $c$ such that for all $p_n/q_n$, $\displaystyle{\frac{c}{q_n^{2.5}}<\left|M-\frac{p_n}{q_n}\right|}$

Using (1) and (2) we conclude that for all $n$,

$\displaystyle{0

But as $q_n\rightarrow \infty$, this inequality cannot hold. Hence $M$ is transcendental.

This number, $0.123456789101112...$ is also known as Champernowne’s constant. It is an example of what we call Normal numbers. I shall discuss more about it in future posts.