Computability

• “A function is computable if can be computed with a Turing machine”

• http://www.ams.org/new-in-math/cover/turing.html

• Valid input -> algorithm -> correct output

• Some problems are not computable

• Halting problem