Next | Topology of Data Types | 9 |

The complement of a semidecidable is

**not**necessarily semidecidableThis 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

Next |