| Next | Topology of Data Types | 6 |
A property is semidecidable if there is a semi-algorithm that can correctly say yes"
Given x, it is guaranteed to halt and say "yes" for all x that have p
If x does not have p, it may halt and say "no"
It may also run forever
The class of semidecidable problems is huge
Typical example: (Hilbert's 10th problem)
Given a diophantine equation,
does it have a solution?
| Next |