Turing machine halts on input $a^m$ with $a^{m^2}$ written on tape

Question

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?

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.