Turing machine accepting square

Question

I'm trying to figure out following assignment and I could use your help, because I'm stuck.

Task:

Construct a Turing machine accepting words in format $1^k$, where $k=n^2$, $n$ being an integer. Basically it accepts those words, where you can arrange ones into square. For example first three acceptable words will be:

1Δ; 1111Δ; 111111111Δ;

My thoughts:

If I get "1" only once, it should be accepted.

Tape: 1Δ; k=1, n=1 and k=n^2

So I m assuming after one "1" I'm in the "STOP" state (lets call it state A) if there is no other char on the tape.

The next acceptable word is the next square, which we I can write in the formula like this:

(n+1)^2 That equals: n^2 + 2n + 1 Difference between two consecutive squares is (2n + 1)

So If my assumption is correct, If I'm in state A I need to somehow check if I get (2*n + 1) times "1" on tape and if that takes me back to state A, it will be correctly accepted. Anything else should be declined.

The problem I'm facing is, that I don't know, how to count (2*n + 1) times "1" on tape.

Also I should find solution using only one tape. The hint is that it should end in the form 111#111111111Δ, where the left side sum of ones equals "k" and right side equals "n". Sadly, this hint didn't help me at all. I'd say it made things worse for me.

Answer 1

It is indeed a good idea to see that $(n+1)^2 = n^2 + (2n + 1)$.

A program in pseudocode for testing square could be:

d = 1
dsqr = 1
while dsqr ≤ n:
   if dsqr = n:
      return true
   dsqr = dsqr + 2d + 1
   d = d + 1
return false

However, the previous code raise the following questions:

• How to keep track of the value d?
• How to keep track of the value dsqr?

Here's an idea (# denote blank symbol):

Tape	Description
#11111111111#	Initial input
#21111111111#	$d = 1$, $d^2=1$
#22331111111#	$d=2$, $d^2 = 4$
#22233333311#	$d=3$, $d^2 = 9$
#22223333333#	$d=4$, $d^2 >n$, reject

In the table, the number of 2 represents the value of $d$, and the total number of 2 and 3 represents the value of $d^2$. When incrementing $d$, one must do the following steps:

• for each 2, add two 3 at the end of the sequence of 2…23…3. During this step, it could be usefull to use another symbol, say 2' to keep track;
• replace the first 3 with a 2;
• add one last 3 at the end.

If the last step reach a blank symbol before finishing, then the input is not a square. If the last step finishes by replacing the last 1, then the input is a square.

I will let the details of the Turing Machine to you.