Decidability
A predicate (problem) A(x1,x2,…,xn) is said to be decidable (solvable)
iff there is an algorithm (program, procedure) such that for any
particular values a1,a2,…,an for x1,x2,…,xn it tells us whether
A(x1,x2,…,xn) is true or false.
Perhaps all the predicates you have seen so far are decidable:
- “x is the gcd of y and z” (n=3)
- “all prime numbers are even”
- Goldbach’s conjecture (n=0)