Next | Topology of Data Types | 6 |

A property is

**semi**decidable 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 |