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)

  • 1
    $\begingroup$ 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. $\endgroup$ – lulu Mar 23 '18 at 9:54
  • $\begingroup$ @lulu Yes, thanks for your comment. I was actually thinking of an initially blank tape, but I should have specified it. $\endgroup$ – 57Jimmy Mar 23 '18 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.

  • $\begingroup$ 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? $\endgroup$ – 57Jimmy Mar 23 '18 at 10:07
  • $\begingroup$ @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$. $\endgroup$ – Arthur Mar 23 '18 at 10:14
  • $\begingroup$ Yes, sure, but as I answered to lulu, I was actually thinking of an initially blank tape $\endgroup$ – 57Jimmy Mar 23 '18 at 14:34

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

  • $\begingroup$ Thanks for your answer. I was actually interested in the sequence of the states of the machine, not of the outputs. I assume there is some way to get around this, but I don't know how $\endgroup$ – 57Jimmy Mar 23 '18 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.