How to compute the language {ww | w ∈ {0,1}*} within a Multitape Turing Machine?

Question

I'm trying to compute a language defined as { ww | w ∈ {0,1}* } in JFlap using a Multitape Turing Machine. It seems a hard problem because there is no delimiter to know when the word w is ended.

I already checked this and this question, but this didn't helped me at all. The answers from "Construct Turing Machine which accepts the language $ww$" talks about deterministic machines and one answer just cite non-deterministic, but dont give details on how this design can be achieved for the given problem.

I've found this algorithm, but this seems very confusing for me (I don't understand the first stage (for example), so I can't reproduce this answer at JFlap).

// Stage 1: Check length is even, change as / bs to As / Bs
while a or b {
    change a to A or b to B & move R
    while a or b move R
    move L
    change a to A or b to B & move L
    while a or b move L
    if A or B move R
}

// Stage 2: Change As and Bs in first half to as and bs
if Blank halt
if A or B move L
while A or B change to a or b & move L
if Blank move R

// Stage 3: Compare first and second halves
while true {
    if a {
        change a to A & move R
        while a or b or Blank move R
        change A to Blank & move L   // fail if B
        while a or b or Blank move L
        if A or B move R
    } else if b {
        ... similarly ...
    }
}
if Blank halt

Can someone clarify this question to me? How can I achieve the first stage in a multitape Turing machine? How can I proceed to solve the problem?

P.S: It must be a multitape Turing machine.

Answer 1

Regarding the first part:

// Stage 1: Check length is even, change as / bs to As / Bs

and

// Stage 2: Change As and Bs in first half to as and bs

Are to find the word middle, then just compare the first half against the second half. Here is a SIMILAR picture for you at JFLAP:

As you can see, at state "q2", I came back to the tape's beginning, to really starts the computation at the state "q3".

After got at the state "q3" you can jump straight to you algorithm part:

"// Stage 3: Compare first and second halves" 

And complete your Turing Machine. But this was your question 1.a) and now you want to solve the question 2.a)

To do it, you will only need to use the step "// Stage 3: Compare first and second halves", from you algorithm.

To do it using a Multi-Tape Turing Machine, you are going to need 4 tapes, the word is to be placed at the tape 1 and the others tapes must to be clean, i.e., contain only blank symbols:

First step, if the tape 1 has only the blank symbol, accept the language.

Second step, if the only symbol not marked at tape 1 is the blank symbol, reject the language.

Third step, is to copy the first symbol not marked from the tape 1 to the tape's 2 end. Then mark it at the tape 1.

Fourth step, is to copy the whole tape 1 to the tape's 3, and the tape 2 to the tape 4.

Fifth step, is to compare both tapes 3 and 4 are equal using yours algorithm step "// Stage 3: Compare first and second halves", but instead of failing to accept the language, go to the step Sixth.

Sixth step, if they are equal accept the language. If they are not, go to the Second step.