Semidecidable sets

• The complement of a semidecidable is not necessarily semidecidable

• This program does not semidecide ¬A:

          if A(x): then
            NO
          else
            YES

• Think of Gödel's theorem for example

• We will now pause to make sure everyone understands this crucial point

• In fact, both A and ¬A are semidecidable if and only if A is decidable