Semidecidability

Given a string S,
is it a theorem of arithmetic?

• To semidecide this, just start generating every possible proof.

• If S is a theorem, you will eventually find it.

• Gödel's first incompleteness theorem:

This property is semidecidable, but not decidable.