I am doing an assignment for my 1st year langauges and automata class. I have been having trouble with the last question which is this: Create a Turing machine that acccepts more a's than b's. I think I am supposed to pair the a's and b's together and then do some more but I can't wrap my head around it. Would help greatly if someone can post the algorithm and explain a little.
Sit before a big empty sheet of paper. Write down a sequence of a's and b's. Now mechanically check whether that string should be accepted. You cannot use counting, that would be requiring an infinite number of "states" inside your head. You can however use additional symols. A striked out b is just a new symbol that is written on the tape.
Turn your intuition into an algorithm. First informally, that is what Karolis has done. Then add information on how to implement this on a Turing tape. What direction is the head moving? Where will it stop? Then translate the whiles and untils into states and transitions (sort of goto-programming, which is improper unless you are programming a TM).
If you are a CS student, then you can do these steps. You can program. No matter whether it is C++, assembler, or Turing. That is just details.
When I was a TA for a course on this stuff, I always recommended students think about it in terms of how you'd recognize patterns of colored marbles. This problem becomes: how do you recognize a row of marbles with more red marbles than blue marbles?
There are lots of approaches to such a problem. You could first count the red marbles, and then count the blue marbles. If you're allowed to give a multi-tape TM for this problem, this is a pretty straightforward solution:
while not at the end of the tape do if marble is red then write a symbol to the red auxiliary tape move the red auxiliary tape head to the right if marble is blue then write a symbol to the blue auxiliary tape move the blue auxiliary tape head to the right move the input tape head to the right rewind the red tape to the front rewind the blue tape head to the front until you reach the end of the red tape do move the red tape head to the right move the blue tape head to the right if at the end of the blue tape and not at the end of the red tape then return Accepted return Rejected
If you'd rather have a single tape solution, other procedures might lend themselves better to this problem. How else might you tell whether you have more blue or red marbles? As another answer points out, you can remove one blue and one red marble from the row of marbles, and repeat until you run out of one color of marble. This looks something like this:
while true do // forever enter the green state while not at the end of the tape do move the tape head right if in the green state and marble is blue then enter red state replace with green marble else if in the green state and marble is red then enter blue state replace with green marble else if in the red state and marble is red then enter black state replace with green marble else if in the blue state and marble is blue then enter black state replace with green marble if in the red or green states then // red state means we needed a red and didn't find one; #red < #blue // green state means that we removed all marbles and // had as many red as blue; #red = #blue return Rejected else if in the blue state then // blue state means we needed a blue and didn't find one; #red > #blue return Accepted else // in the black state, so we removed a red and a blue; // there may still be marbles to remove, so we start over. rewind the tape head to the beginning
Are there other possibilities? Sure there are. You could first sort the marbles to make it easier to find pairs, for instance. Remember: as far as we know, human beings can't do anything computationally more powerful than what a TM can do. That means that if you can answer this question for an arbitrary sequence of marbles, so can a Turing machine :)