Next | Topology of Data Types | 4 |

A property

*p*is**decidable**if for any*x*you can say whether it has the propertyThere must be an algorithm

It

**must terminate**for all*x*in the domainWhen it terminates, it must emit the

**right answer**

Decidable properties include:

Is the integer

*n*prime?Is

*n*an integer of the form 2^{i}3^{j}, where the decimal expansion of*i*/*j*contains no 7s?Does the graph

*G*have a Hamiltonian cycle?Is the

*n*th digit in the decimal expansion of a seven?

Next |