How to distinguish empty cells from cells outside of the input cells?

Question

Setup

I need to develop a Turing Machine that accepts a string m that has the same number of a's and b's. My alphabet is {a,b}, and we use a diamond in class to represent an empty space.

Problem

The part I'm having trouble with is returning to the beginning of the string.

So far

At first I was planning on taking a character(a) marking it with a diamond, moving right until the other character(b) is found, marking that with a diamond, then moving left until the other's other character(a) is found, and repeating the process. The parenthesis are for example, it could have been b,a,b just as well.

Then at the end if there is an outlier I will know the number of a's and b's was not similar.

But then I developed an example language ab... and realized that this process will never end in this case, so instead I need a way of determining when I have reached the beginning of the string.

So now my question...

Is it possible to determine when I have reached the beginning of the string without introducing another letter into the alphabet, or another special character like the diamond?

Answer 1

I think it's intuitively clear that it's not possible. You have to be able to distinguish working and "outside" part of the tape, and on both sides!

There are two common ways to solve this:

• Assume the input is delimited by special characters.
• Overwrite with a new special tape symbol.

Both are fair and there is no reason not to.

Answer 2

The common definition of the Turing machine is that when you go left when you're at the furthest left point on the tape, is to stay on that spot. So if you want to determine where it began, mark it off, as you said, with a diamond or similar.