Decidability

• 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 2ⁱ3^j, 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?