|Next||Topology of Data Types||4|
A property p is decidable if for any x you can say whether it has the property
There must be an algorithm
It must terminate for all x in the domain
When it terminates, it must emit the right answer
Decidable properties include:
Is the integer n prime?
Is n an integer of the form 2i3j, where the decimal expansion of i/j contains no 7s?
Does the graph G have a Hamiltonian cycle?
Is the nth digit in the decimal expansion of a seven?