4
$\begingroup$

For example, if I have a start state of $i$ and a string $w$, how could I create a Turing machine that would halt when the tape content is $w \Box w$? The language is $\{a,b\}$.

My initial idea was a machine that:

On $i$, moves right and changes to $p$.

On $p$, if letter read is $a$, move $n+1$ cells to the right and change to $x$.

On $p$, if letter read is $b$, move $n+1$ cells to the right and change to $y$.

On $p$, if $\Box$, change to $h$.

On $x$, write $a$, move $n$ cells to the left and change to $p$.

On $y$, write $b$, move $n$ cells to the left and change to $p$.

On $h$, halt.

However, I don't think it'll work because Turing machines aren't allowed to move more than 1 cell at a time. Any help would be appreciated.

$\endgroup$
1
$\begingroup$

You are pretty close, here is a TM deciding the language (pseudocode):

  1. Check the input contains a single $\Box$,

    • If false, reject.
  2. Zig-zag across the tape, check identical letters, and replace them by $X$.
    • If not identical, reject.
  3. When all the letters left of $\Box$ are marked $X$, check for remaining letters right of $\Box$
    • If there are remaining letters, reject.
    • Otherwise, accept
$\endgroup$
0
$\begingroup$

How can you move exactly $n+1$ squares? Put a special mark at the end before you leave, then move back to the mark.

How can you remember which character to copy? You have a finite alphabet, so duplicate the states you use for each character. For example, you'll be in $p_a$ when copying character $a$ and in $p_b$ when copying character $b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.