I am learning Turing machine in automata. Following problem might be simple, as that's the first question on Turing machines in my textbook, however I am not sure if I am doing it efficiently.

Give Turing machine with input alphabet {a} that on input $a^m$ halts with $a^{m^2}$ written on its tape.

My approach: The machine will first move right seeing an a on each position on tape. So there will be $m+1$ states $q_0$ to $q_m$ defined, on which the machine will move sequentially seeing an $a$. If machine meets the end of the string seeing an empty position at state $q_m$, it will move left $\sqrt{m}$ times, and halt.

The problems,

  1. $m$ is not given here, so m can be anything, $1,4,9,25,..$, infinite possibilities. How many states shall I define then?
  2. As the Turing machine can not calculate $\sqrt{m}$, I am defining newer states like $q_{41},q_{42}$ etc (If the Turing machine sees end of string at state $q_4$, then it moves left to state $q_{41}$, then to $q_{42}$, then it halts). This way also, many numbers of states to be defined, as $\sqrt{m}$ increases with $m$. So my transition table is becoming huge and infinite.

Can someone suggest a better way to define this Turing machine?


1 Answer 1


What you give is not a Turing machine since the number of states is not fixed but rather it depends on the length of the input.

Here is a possible Turing machine that solves the problem. Its tape alphabet is $\{\varepsilon, a, a', b, t, t'\}$ where $\varepsilon$ denotes the blank symbol, $a'$ can be thought as a special $a$ symbol that has been already "processed", and $t$, $t'$ are temporary symbols.

It is convenient to first describe a simpler subroutine. If the tape contains $m$ symbols that are either $a$s or $a'$s then the following subroutine appends $m$ $b$s to the tape. First repeat the following:

  • Search for the leftmost $a$ or $a'$, if any. This can be done by moving left until $\varepsilon$ is found, then moving right until one of $a$, $a'$, or $\varepsilon$ is found.
  • If no $a$ or $a'$ exists then exit the loop.
  • If the current symbol is $a$, replace it with $t$. Otherwise replace it with $t'$.
  • Move right until the first $\varepsilon$ symbol is encountered.
  • Replace the current symbol with $b$.

At the end of the loop replace all $t$s with $a$s and all $t'$s with $a'$s.

The final Turing machine repeats the following steps:

  • Search for the leftmost $a$, if any.
  • If no such $a$ exists then exit the loop.
  • Replace the current symbol with $a'$.
  • Invoke the above subroutine.

At the end of the loop replace all $a'$s with $\varepsilon$s and all $b$s with $a$s. Halt.

  • $\begingroup$ Not getting how it is halting at $\sqrt{m}$ position. Looks to me it is shifting all $a$'s to right by $m$ positions. However thanks for giving the idea that temporary terminals can be used by Turing machine to work out a logic. $\endgroup$
    – Sukti Sen
    Commented Jun 30, 2021 at 5:52
  • $\begingroup$ From the statement of your problem it seems like when the input of your machine is $a^m$, it needs to compute $a^{m^2}$. Correct me if I'm wrong. The Turing machine in my answer does that, i.e., it computes the square not the square root. $\endgroup$
    – Steven
    Commented Jun 30, 2021 at 7:47
  • $\begingroup$ ok. May be I perceived the problem wrong. $\endgroup$
    – Sukti Sen
    Commented Jun 30, 2021 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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