To illustrate some of the key challenges in computing with Turing machines and
how to overcome them, we'll examine this task here,
where we're given an input string, and
we want to tell if it is of the form w#w, where w is a binary string.
Otherwise, we reject it.
I'll illustrate the basic idea on this example.
First, we x out the first symbol on the tape.
And then we're going to go look to see if the first element past the #
is the same symbol.
So the fact that I read a 0 here,
somehow has to encoded in the machine's state.
So we'll go along to the first symbol after the # and indeed it is a 0.
If it wasn't, then we can reject the input right away.
Those two strings on either side of the # are not equal.
We x out that 0, so that we know not to check it again.
And we move left, past the #,
over to the first x after that that we encounter.
And now we're ready to repeat that process.
We x out the 1 this time.
Remembering the fact that it was a 1 in the machine state.
We can forget that the previous symbol was a 0 by now.
And then we move right, past the #,
past all the x's, to the next non-x symbol that we see.
This is a 1, which matches what we x'd out before.
That's great.
We x it out and then we rewind past the #, to the first x that we encounter.
At this point, the next symbol is a #, so we know that the string to
the left of the # matches the first part of the string to the right.
But, there might might be more to the right, so
we check that we crossed off all of the 0's and 1's to the right of the #.
If we didn't, then we reject because there wasn't a match.
The string on the right was too long.
As Turing machines go, this is a pretty simple program, but
as you can see here, the state diagram gets a little messy.
Like the Sipsor text book, I have used a little shorthand here in the diagram.
When two symbols appear to the left of the arrow, I mean,
to match either one those.
It's easier than writing out a whole other edge.
Also, sometimes I will only give a direction on the right,
interpret that to mean that the tape should be left alone.
Here is our initial state, q0.
>From here, we usually read either a 0 or 1, and
proceed down one of these two parallel paths.
We need parallel paths here, because we have to remember whether it was a 0 or
a 1 that we read initially.
We move past the rest of the first string to the # and
then past any x'd out symbols to the next either 0 or a 1.
Actually, if we encounter a blank,
that means that the second string was too short and we can reject immediately.
Or if we encounter a 1 when we're looking for
a 0, that also means that we reject.
If we encounter a 0 in this side, however,
that means that we found a match and we can begin the rewind process.
And this path is exactly an alogus.
When we do find the match, we x it out, and then begin the rewind process.
Rewinding past all the xs.
Then we encounter a #, and then we rewind past all the 0s,
and 1s until we encounter the first x.
And then we move the symbol to the right so
that we're reading the next symbol in the first string that was input.
And then we're ready to begin this process again.
When in this phase, we encounter the #.
That means that we've matched all of this first string, here.
And so we just need to check that this string here isn't any longer.
So we moved past all the xs and if we encounter a blank next, that's great,
we accept.
If we encounter something else, then we need to reject.
Take a minute to look this all over carefully and
convince yourself that it's right.
It helps to trace through an example.
We'll do this for the input 01#01.
Of course we start in the initial state q0, and we read a 0,
so we transition to the state q1, xing out that 0.
So this becomes our new configuration.
Next, we read a 1 so we stay in this state and
just move the head to the right.
Next we encounter the #, so we move to state q3 and move the head to the right.