Take the 2-minute tour ×
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.

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

closed as unclear what you're asking by D.W., Rick Decker, Juho, András Salamon, lPlant Jul 22 at 13:57

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
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
1  
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
1  
@Merbs If you only have a finite memory, you cannot determine whether a string contains the same number of $0$s as $1$s. If you could do that with finite memory, the language would be regular and a standard proof by the pumping lemma shows it isn't. –  David Richerby Jul 21 at 13:38

4 Answers 4

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
  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

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

This is one example i made for my upcoming exam in cs which can be tested here

It alternates between marking a 0 and a 1 with x. If it finds no more 0s it checks if there are any remaining 1s and switches to an accepting or declining state respectively.

;search for 0 from left to right and replace with x
0 0 x * 2
0 1 1 r 0
0 x x r 0
0 _ _ l 4

;search for 1 from left to right and replace with x
1 0 0 r 1
1 1 x * 3
1 x x r 1
1 _ _ * declined ;because 0 was found, 1 was not -> uneven # -> decline

;0 was replaced! back to the leftmost position
2 0 0 l 2
2 1 1 l 2
2 x x l 2
2 _ _ r 1

;1 was replaced! back to the leftmost position
3 0 0 l 3
3 1 1 l 3 
3 x x l 3
3 _ _ r 0

;state 0 found no more 0s -> go back to leftmost position to check for remaining 1s
4 0 0 l 4
4 1 1 l 4 
4 x x l 4
4 _ _ r 5

;state 0 found no more 0s and state 4 moved back to leftmost position: any 1s left? -> decline, no 1s left? -> accept 
5 1 1 * declined
5 _  _ * accepted
5 x x r 5
5 0 0 r 5 ;for the sake of determinism ;)

;endless loops to see the result
accepted * * * accepted
declined * * * declined

SYNTAX:

  • Syntax: <current state> <current symbol> <new symbol> <direction> <new state>
  • ';' starts a comment.
  • '*' is a wildcard: it matches any symbol/state when used in the current symbol/state field; it means 'same as current' when used in new symbol/new state field.
  • '_' represents the blank (space) symbol.
  • Symbols must be a single non-whitespace character except ';'.
  • States can be any word, not only numbers.
share|improve this answer

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