Semidecidable sets

• Say that a set of strings is semidecidable if membership in the set can be semidecided

• (This is equivalent to S being recursively enumerable)

• Semidecidable sets are closed under binary intersection:

• To semidecide A ∩ B:

      if A(x): then
        if B(x): then
          YES
        else
          NO
      else
        NO