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

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?

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.

• 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. Jun 30, 2021 at 5:52
• 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. Jun 30, 2021 at 7:47
• ok. May be I perceived the problem wrong. Jun 30, 2021 at 8:37