Turing machine accepting perfect squares in unary notation

Question

I'm trying to figure out following assignment and but I'm stuck at solving it:

Task:

Construct a Turing machine accepting words in format 1^k, where k=n^2 n is integer.

Basically it accepts those words, where you can arrange ones into square.

For example first three acceptable words will be:

1Δ; 1111Δ; 111111111Δ;

Which are arrange-able into squares like this:

1

11
11

111
111
111

My analysis

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 (let's call it state A) if there is no other character 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 + 2*n + 1

The difference between two consecutive squares is (2*n + 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.

Question

I think the above is a good approach, but I don't know how to count (2*n + 1) times "1" on the tape. How to do that?

Note that I should find the solution using only one tape.

The hint I got, is that I could use the form:

111#111111111Δ, where the left side sum of ones equals "k" and right side equals "n". But I don't see how this hint helps me.

Answer 1

The way you approached it looks like the way to go.

I don't know how to count (2*n + 1) times "1" on tape.

Realise that the difference between two consecutive squares increases with steps of 2:

• 1 + 3 = 4
• 4 + 5 = 9
• 9 + 7 = 16
• 16 + 9 = 25
• ...

Or otherwise put: an integer square can be written as a sum that starts like this:

1 + 3 + 5 + ...

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"

The two sections approach would work, but it is confusing that the right section is identified as "n", as that represents the square root of k in your earlier description. It should represent a kind of remainder of the input.

I would suggest deleting k symbols from the input, and then increase k by 2. The idea is to mark a group of digits that has a size that corresponds to a term of the sum (1 + 3 + 5 + ...), and before deleting it, to copy that many marks, adding 2 more. If this exactly marks all input digits, then we have a match.

To visualise, let's say the input is 9 (111111111), then we go through these alterations of the tape:

111111111
# intial mark:
211111111  

# copy mark and delete original
_21111111  
# mark two more
_22211111  

# copy mark and delete original
____22211  
# mark two more
____22222  

# --> MATCH

To easy the copy phase, mark the last marked digit as "3" instead of "2".

Here is a transition table for this ("_" is blank):

state	read	write	move head	next state
start	1	3	right	check
start	_		left	reject
check	_		left	accept
check	1		left	left
left	2 or 3		left	left
left	_		right	move
move	2	_	right	carry
move	3	_	right	carryLast
carry	2 or 3		right	carry
carry	1	2	left	left
carry	_		left	reject
carryLast	2		right	carryLast
carryLast	1	2	right	addOne
carryLast	_		left	reject
addOne	1	2	right	start
addOne	_		left	reject

And here is a runnable snippet to test it with your own input:

createTuring({
    transitions: [
        { state: "start",     read: "1", write: "3", move: "R", nextState: "check"     },
        { state: "start",     read: "_",             move: "L", nextState: "reject"    },
        { state: "check",     read: "_",             move: "L", nextState: "accept"    },
        { state: "check",     read: "1",             move: "L", nextState: "left"      },
        { state: "left",      read: "23",            move: "L", nextState: "left"      },
        { state: "left",      read: "_",             move: "R", nextState: "move"      },
        { state: "move",      read: "2", write: "_", move: "R", nextState: "carry"     },
        { state: "move",      read: "3", write: "_", move: "R", nextState: "carryLast" },
        { state: "carry",     read: "23",            move: "R", nextState: "carry"     },
        { state: "carry",     read: "1", write: "2", move: "L", nextState: "left"      },
        { state: "carry",     read: "_",             move: "L", nextState: "reject"    },
        { state: "carryLast", read: "2",             move: "R", nextState: "carryLast" },
        { state: "carryLast", read: "1", write: "2", move: "R", nextState: "addOne"    },
        { state: "carryLast", read: "_",             move: "L", nextState: "reject"    },
        { state: "addOne",    read: "1", write: "2", move: "R", nextState: "start"     },
        { state: "addOne",    read: "_",             move: "L", nextState: "reject"    },
    ],
    initState: "start",
    tape: "111111111",
});

<script src="https://trincot.github.io/turing.js"></script>

Answer 2

So if you just want a single-tape machine that you know will work and you don't care about efficiency, consider the following:

1. copy the input to the end of the tape, separated from the original input by a separator
2. write a number k (from 1 on up) in unary on the end of the tape, separated from the copy by a second separator
3. divide the copy by the counter k by iteratively subtracting k from the copy and marking one of the k crossed-off symbols of the copy with a special symbol
4. provided that the division in step 3 left 0 remainder, divide again in the same way but only considering the specially marked symbols
5. provided the division in step 4 left 0 remainder, see if the quotient was 1. if so, you found input = k^2 and can halt-accept. otherwise, you can halt-reject when k > input.

Example on input 1111:

   1111
-> 1111A1111       // copy input
-> 1111A1111B1     // add counter
-> 1111A3333B1     // divide by 1 by bouncing back and forth, marking every 1th
-> 1111A5555B1     // repeat
-> 1111A1111B11    // don't have one 5, so copy input and increment counter
-> 1111A3232B11    // divide by 2 by bouncing back and forth, marking every 2nd
-> 1111A5242B11    // divide by 2 again considering only 3s from last step
-> accept          // halt-accept since one 5 remaining means input = k^2

Your way works too. You can keep track of the current n (or k) and iteratively cross off 2n + 1 of the 1s in your copy at each stage. Something like:

   1111
-> 1111A1111    // copy input
-> 1111A1111B   // begin counter at 0
-> 1111A2111B   // cross off 1 in the copy
-> 1111A2111B1  // increment counter
-> 1111A2222B1  // cross off 3 in the copy
-> accept       // all symbols crossed off

If what's getting you is the actual mechanics of "bouncing back and forth" to cross off, subtract, divide, etc., the idea is that you change the symbol you're crossing off to one you recognize as meaning it has been marked for that purpose; change state so you know what you need to go mark off next; go mark that off; then, return to the first unmarked symbol (if any) where you started.