0
$\begingroup$

I came here to ask for help with a two-tape Turing machine for the following language.

$L = \{ a^{n^2} | n \ge 0 \}$

I tried following the advice on this site: Turing machine that accepts L={an2|n≥1} [duplicate]

because it was the one with the most answers, but I'm still not sure about the algorithm.

If I understood it correctly, both tapes start at the respective beginnings (the 1st tape starts at the first symbol, and the second tape starts at the first "cell" in the tape). So, we move both heads by one, until we get to the end of the counter tape. Then, we add two symbols (markers) to the last two cells on the right of the tape.

My questions are, what do I do after adding two markers to the last two cells on the right of the tape? Do I return both heads to the beginnings of the respective tapes? Also, do I have to go to the end of the counter tape on each iteration, or do I just go to the first marker symbol, and then go back two steps and place markers there?

$\endgroup$

1 Answer 1

0
$\begingroup$

I'll let the mods decide if it's a duplicate or not, but I do agree that the explanations could warrant a bit more explicit explaining.

  1. You have two tapes, one of them is the one with the input, and the other one is to help us advance by $1, 3, 5, \cdots.$ since as they mentioned, $1 + 3 +5 + \cdots (2n+1) = (n+1)^2$

  2. The idea is that the tape that's helping us advance by odd numbers is doing a bunch of bookkeeping to make sure we only advance by odd numbers.

I'll explicitly illustrate how this works for a few runs

We are at an unvisited cell in our first tape, accept if the second input is done (this is up to you how to do it, but you can just move one to the right, check for end, and then come back if it's not the end). As you will see later, you might have to modify the first case a bit depending on how you think about it.

| | | | | |
 ^
|a|a|a|a| |
 ^

Add two markers

|x|x| | | |
   ^
|a|a|a|a| |
 ^

Go back to the start

|x|x| | | |
 ^
|a|a|a|a| |
 ^

This is where we can have off-by-one errors, but I'll be very explicit here.

  1. Advance tape 2
  2. If tape 1 has an x, then advance tape 1 and repeat
|x|x| | | |
   ^
|a|a|a|a| |
   ^

I'll skip a step. Now, we are at an unvisited cell. Remember we always advance tape 2, but we don't do the cycle again unless tape 1 sees an x. In this case, we advanced tape 2 but tape 1 did not see an x.

|x|x| | | |
     ^
|a|a|a|a| |
       ^

Now, we would check tape 2 to see if the input is done. In this case we are done so we accept, but let's just pretend tape 2 had more, then we would repeat our steps for extending the markers on tape 1.

So we fill two more x's

|x|x|x|x| |
       ^
|a|a|a|a|a|
       ^

And we go back and start again

|x|x|x|x| |
 ^
|a|a|a|a|a|
       ^

Hope this helps. There are a few ways to go about doing the off-by-one errors, which I suspect you're confused about, but I think explicitly showing these should be able to get you to your understanding.

$\endgroup$

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.