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

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)

• This seems very broad. If, say, you imagine that your machine is reading a tape and simply moving to the next state described on the tape, then of course it can describe an irrational. The tape might have $\sqrt 2$ written on it, and the machine would dutifully reproduce that. Of course, there are more interesting machines than that but without describing what the machine is doing it's hard to say more.
– lulu
Commented Mar 23, 2018 at 9:54
• @lulu Yes, thanks for your comment. I was actually thinking of an initially blank tape, but I should have specified it. Commented Mar 23, 2018 at 10:03

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.
• Thanks! I guess this answers my question. But I am still wondering if it would be possible to get more interesting numbers, like $e$ or $\pi$. Do you have a guess? Commented Mar 23, 2018 at 10:07
• @57Jimmy Following lulu's idea, if we have a tape which reads $2718281828\ldots$, and use a head which always moves to the right and switches to the state corresponding to the digit it has just read, then the states will spell out the decimal expansion of $e$. Commented Mar 23, 2018 at 10:14
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.