1
$\begingroup$

I'm reading this tutorial from the University of Illinois about Turing Machines, and I don't understand something.

They give a pseudocode algorithm for an machine that accepts strings from the language

$L = {0^n1^n}$

and a diagram of the machine. Both are pictured below:

Turing Machine anbn algorithm

Turing Machine anbn

What I don't understand however is how does this machine know that the number of $0$s are the same as the number of $1$s. I see no mechanism that can do that. All it seems the machine can do is recognize that there are no $0$s after $1$s.

$\endgroup$
  • $\begingroup$ I would suggest that you make up your mind on whether it is $a$ and $b$, or $0$ and $1$, and that you edit the question accordingly. You should probably use $0$ and $1$ since it is used in the diagram. $\endgroup$ – babou Jun 19 '15 at 21:46
  • 1
    $\begingroup$ Please transcribe the first image using code formatting. $\endgroup$ – Raphael Jun 19 '15 at 23:07
  • $\begingroup$ @Raphael can you recommend how I could find out how to do that? $\endgroup$ – CodyBugstein Jun 19 '15 at 23:09
  • $\begingroup$ Sure. Just click the little question mark above the textbox you reach by clicking "edit" beneath your post. $\endgroup$ – Raphael Jun 19 '15 at 23:12
  • 1
    $\begingroup$ What have you tried? Have you tried running the machine by hand on a few inputs, to see what it does? This should be your first step. We expect you to make a serious effort to answer your question on your own before asking here, and to tell us what you tried and where you got stuck in the question. $\endgroup$ – D.W. Jun 19 '15 at 23:39
3
$\begingroup$

It might be helpful to see what happens when the machine encounters $0^31^3$, say:

  1. Initial state: $000111$.
  2. Mark the first unmarked zero: $A00111$.
  3. Mark the first unmarked one: $A00B11$.
  4. Mark the first unmarked zero: $AA0B11$.
  5. Mark the first unmarked one: $AA0BB1$.
  6. Mark the first unmarked zero: $AAABB1$.
  7. Mark the first unmarked one: $AAABBB$.
  8. There are no unmarked zeros and no unmarked ones, so accept.

In contrast, here is what happens on input $00011$:

  1. Initial state: $00011$.
  2. Mark the first unmarked zero: $A0011$.
  3. Mark the first unmarked one: $A00B1$.
  4. Mark the first unmarked zero: $AA0B1$.
  5. Mark the first unmarked one: $AA0BB$.
  6. Mark the first unmarked zero: $AAABB$.
  7. Crash (reject) since there are no remaining unmarked ones.

And here is what happens on input $00111$:

  1. Initial state: $00011$.
  2. Mark the first unmarked zero: $A0111$.
  3. Mark the first unmarked one: $A0B11$.
  4. Mark the first unmarked zero: $AAB11$.
  5. Mark the first unmarked one: $AABB1$.
  6. There are no unmarked zeroes but there is an unmarked one, so crash (reject).
$\endgroup$
4
$\begingroup$

The machine just changes the $O$ to $A$ and the $1$ to $B$, in such a way that it changes a $1$ each time it has changes a $0$. Hence, if there is the same number of $0$ and $1$, they all end up being changed at some point. The TM no longer finding any $0$ will go to the bottom part of the diagram and check that all $1$ have been changed to $B$, i.e. that the sequence of $B$ is followed by a blank space. In that case it accepts.

But is some $1$ is left after the $B$, then the TM will block in state $q_3$ (no transition corresponding to $1$ on the tape) and reject. Indeed, that means hat there were more $1$ than $0$, which does not conform.

But if there were more $0$ than $1$, say $0^n1^m$ with $n>m$, the TM will block in state $q_1$. The reason is that, after erasing $m$ symbols $0$ and correspondingly $m$ symbols $1$, the TM will erase another $0$, and try in state $q_1$ to find another $1$ to erase. But it will find none, only a blank space.

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