Why is Entscheidungsproblem undecidable not semi-decidable?

Question

Let's say checking if a proof is valid is decidable. Then surely we can just enumerate the proofs then check if it's valid. This seems to be a semi-decidable procedure. But why Entscheidungsproblem is undecidable then?

Answer 1

There is a lot of terminology, and a lot of redundant terminology, in computability theory. Briefly, here's the situation:

• Decidable, recursive, and computable are all equivalent.

• Semidecidable, recognizable, recursively enumerable (r.e.), and computably enumerable (c.e.) are all equivalent.

In general, the "computation"- and "recursion"-centered terminologies are the standard ones - with the former more modern than the latter. So in the modern literature you'll see references to r.e. or c.e. sets, but rarely to semidecidable sets.

• A set with c.e. (or etc.) complement is called co-r.e. or co-c.e.; I've not seen "co-semidecidable" before, but I wouldn't be surprised if it occurred.

• There is no specific term for non-c.e. (or etc.). You just say "non-c.e."

Answer 2

It is both.
"Decidable" means "both semi-decidable and co-semi-decidable". "Undecidable" means "not semi-decidable or not co-semi-decidable or neither".
The Entscheidungsproblem is semi-decidable: We can enumerate all valid inferences. But it is not co-semi-decidable: We can not enumerate all invalid inferences. So it is undecidable but semi-decidable.