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Δ;
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.