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.

  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Commented Nov 26, 2021 at 10:48
  • 1
    $\begingroup$ i added my try. @Nathaniel $\endgroup$
    – snirben
    Commented Nov 26, 2021 at 10:58
  • $\begingroup$ Please credit the original source of all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Commented Nov 26, 2021 at 22:54
  • $\begingroup$ cs.stackexchange.com/q/138969/755 $\endgroup$
    – D.W.
    Commented Dec 24, 2021 at 1:39
  • 2
    $\begingroup$ Does this answer your question? Turing machine for unary encoded quadratic numbers $\endgroup$ Commented Dec 26, 2021 at 17:48

1 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.


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.