Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

Design a program for a Turing machine.

Create a decision procedure for the set of binary strings which contain the same number of 0's and 1's.

Please help! Thanks.

I am a beginner student and have no idea where to start. So sorry for how elementary this is.

share|improve this question
Do you have a textbook? Have you seen the definition of Turing Machines or an example of one and how it works? – usul Dec 5 '12 at 3:50
I do not have a textbook, but I do have a basic understanding of how Turing machines work. We have to write a program with a bunch of instructions such as <p,1,B,R,q>. This particular instruction would mean that when in state p and scanning a 1, the machine prints a blank, moves one space to the right, and switches to state q. – David Kent Dec 5 '12 at 3:59
Great! Then you do have a good idea of where to start. A good next step is to ask yourself how you would solve the problem; can you write down a series of step-by-step instructions for another person to follow that would enable them to get the right answer? Once you can do that, you can start thinking about how to get a machine to do it. But your instructions need to be very specific! E.g. bad: "write down the number of zeroes". good: "starting from the left end, find the first zero". – usul Dec 5 '12 at 4:25
Imagine you have a really long string 11101101011010000101000010101010101001011010111101111100001011010100010001000100‌​01110101010101... How would you determine if it had an equal number of 1s and 0s? One way you could do it is to count all the 1s and then all the 0s, but suppose you have a finite memory (can only remember numbers up to some $k$) but the string can by arbitrarily long. What's another way? – Merbs Dec 5 '12 at 4:50

3 Answers

up vote 1 down vote
  1. Write "L" on the left of the string and "R" on the right.
  2. Go from L to R, see if there are any 0s or 1s between them.
  3. If there are no 0s or 1s (empty string), accept.
  4. If there are 1s, but no 0s, reject.
  5. If there are 0s, but no 1s, reject.
  6. If there are both 0s and 1s, then scroll back from R to L and erase the first 0 and the first 1 you encounter.
  7. Goto step 2.
share|improve this answer
up vote 1 down vote

Thinking like a TM

When you try to come up with a TM for something, you're generally not worried about efficiency... you just want to demonstrate that whatever you're computing can be computed by a TM. So you want to try to think of the easiest thing a TM could do to compute what you want.

Let's say you're allowed to come up with a multi-tape TM. Multi-tape TMs can be reduced to single-tape TMs, after all, so the existence of a multi-tape TM guarantees there's a single-tape one. A simple way to tell whether you have the same number of 0s as 1s is to count the 0s and count the 1s and see whether you have the same number. TMs are pretty great at counting in unary, i.e., by ticks. You could use two extra tapes (beside the input tape) to count the 0s and 1s as you read the input tape; then, step through the two auxiliary tapes one symbol at a time. If you see the same number of symbols in both tapes, you're good, and accept. Otherwise, you reject.

Let's say you'd prefer a single-tape TM directly. How can you tell you have the same number of 0s as 1s without counting? Well, one way would be to remove a 0 and remove a 1, over and over again, until either nothing is left, in which case you accept, or there are only symbols of one kind remaining, in which case you reject. To do this, you could have the TM start at the first symbol, replace it with some other symbol (2, maybe; anything you like), and then scan right for the opposite symbol. If you don't find one, you reject; if you do find one, you replace it with your replacement symbol, return to the front of the tape, and start over. You always ignore (skip over) your replacement symbols. If you get to the end of the input and have replaced all 0s and 1s with your replacement symbol, then you accept.

Other possibilities exist. Just remember, you want to think of the easiest way possible in which to do this. Don't worry about finding a clever, efficient TM... that's what C++ is for.

share|improve this answer
up vote 0 down vote

I suggest that in order to have a clear view in your mind about what the instructions you would write should do, firstly construct a "state" diagram (as you will see if you go through the Wikipedia page for Turing Machine). This will help you understand which sequence of symbols should lead you to the correct final state and either accept or discard the given string. As an extra help on diagrams, I think you should check DFAutomation to understand how you should construct your own.
And an extra hint: You can deal with this problem as an "open as many '(' as you like and check if all of them are closed (you have the same number of ')' ) inside the given string".
This is a question I faced in another course, and solved it using push-down automata.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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