Can the sequence of states of a non-halting Turing machine describe an irrational / transcendental number?

152 Views Asked by At

Let $T$ be a Turing machine (or another type of more suitable machine, I am not very confident with this field) with $n$ states and assume that, when started on a blank tape, $T$ does not halt. Interpret the sequence $(x_k)$ of its states (not the number it writes!) as a "decimal" number in basis $n$ (for simplicity, we could assume $n=10$).

(1) Is there any constraint on $(x_k)$? In particular, can it describe an irrational or even a transcendental number?

(2) Could this approach be useful in proving some results about irrationality / transcendence of numbers? (For instance, proving that a number is not irrational by describing it as $(x_k)$ for some Turing machine)

2

There are 2 best solutions below

3
On BEST ANSWER

Take a Turing machine which goes to the left until it finds a blank cell, writes a 1, then goes to the right until it finds a blank cell, writes a 1, then repeats. It will need two states for this behaviour ($l$ for "moving left", and $r$ for "moving right"), and when run on a blank tape, initially in state $l$, it will have the following states: $$ lrllrrrllll\cdots $$where each run of consecutive states is one longer than the pevious one. Interpreting this as an expansion in some fixed base, say $.10110001111\ldots$ in base two or base ten, will necessarily give an irrational number. Is it trancendental? Probably.

1
On

Certainly you can get $e$ or $\pi$. It's possible to compute as many decimals as you want in Python, right? Or more precisely to the point, there exists a non-halting Python program that prints the digits one by one. Of course the Church-Turing thesis is too fuzzy to be amenable to proof, but it's a fact that anything a Python program can do can also be done by a Turing machine.

(Some people find programming in Python easier...)