turing-machines

Turing machine - more 0 or 1?

let's say we have a tape of: xx01101011xx (x is an empty character). Could you give me an idea of an algorithm, that would say whether there's more 0 or 1? I heard about "pairing" method, but I have no idea how to use it.

Regards.

Solution

  • If the left-most non-blank non-X character is a 0 search right for a 1, if found change both to Xs.

    If the left-most non-blank non-X character is a 1 search right for a 0, if found change both to Xs.

    If a match can't be found then the left-most non-blank character exists in greater amounts. If the entire tape ends up with Xs then they exist in equal amounts.

    EX with _ as blank, alphabet of {0,1,X}:

    __01101011__
     v
__XX101011__
     v
__XXXX1011__
     v
__XXXXXX11__
     v
No matching 0 found, more 1s