1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ What is the example language that you developed? $\endgroup$
    – Steven
    Apr 22 '13 at 21:26
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, that is how I was thinking about it but I wanted to make sure I wasn't missing something. As the assignment doesn't specify that we can or cannot do this. I'll get back here too when the solutions are posted next week. $\endgroup$
    – clark
    Apr 25 '13 at 2:12
1
$\begingroup$

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.

$\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.