# Turing machine accepting square

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

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.

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Nov 26 '21 at 10:48
• i added my try. @Nathaniel Nov 26 '21 at 10:58
• Please credit the original source of all copied material: cs.stackexchange.com/help/referencing
– D.W.
Nov 26 '21 at 22:54
• cs.stackexchange.com/q/138969/755
– D.W.
Dec 24 '21 at 1:39
• Does this answer your question? Turing machine for unary encoded quadratic numbers Dec 26 '21 at 17:48

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.