Semidecidable

---

}} A property of a theory or logical system weaker than decidability is semidecidability. A theory is semidecidable if there is a well-defined method whose result, given an arbitrary formula, arrives as positive, if the formula is in the theory; otherwise, may never arrive at all or arrives as negative. Equivalently, a logical system is semidecidable if there is a well-defined method for generating a sequence of theorems such that each theorem will eventually be generated. This is different from decidability because in a semidecidable system there may be no effective procedure for checking that a formula is not a theorem.

Every decidable theory or logical system is semidecidable, but in general the converse is not true; a theory is decidable if and only if both it and its complement are semidecidable. For example, the set of logical validities V of first-order logic is semidecidable, but not decidable. In this case, it is because there is no effective method for determining for an arbitrary formula A whether A is not in V. Similarly, the set of logical consequences of any computably enumerable set of first-order axioms is semidecidable. Many of the examples of undecidable first-order theories given above are of this form.

In computability theory, a set S of natural numbers is called semidecidable if:

• There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S.

Or, equivalently,

• There is an algorithm that enumerates the members of S. That means that its output is a list of all the members of S: s₁, s₂, s₃, ... . If S is infinite, this algorithm will run forever, but each element of S will be returned after a finite amount of time. Note that these elements do not have to be listed in a particular way, say from smallest to largest.

The first condition suggests why the term semidecidable is sometimes used. More precisely, if a number is in the set, one can decide this by running the algorithm, but if the number is not in the set, the algorithm can run forever, and no information is returned. A set that is "completely decidable" is a computable set. The second condition suggests why computably enumerable is used. The abbreviations c.e. and r.e. are often used, even in print, instead of the full phrase.

A set S of natural numbers is called semidecidable if there is a partial computable function whose domain is exactly S, meaning that the function is defined if and only if its input is a member of S.

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.^[1]

A decision problem is a question which, for every input in some infinite set of inputs, requires a "yes" or "no" answer.^[2] Those inputs can be numbers (for example, the decision problem "is the input a prime number?") or values of some other kind, such as strings of a formal language.

The formal representation of a decision problem is a subset of the natural numbers. For decision problems on natural numbers, the set consists of those numbers that the decision problem answers "yes" to. For example, the decision problem "is the input even?" is formalized as the set of even numbers. A decision problem whose input consists of strings or more complex values is formalized as the set of numbers that, via a specific Gödel numbering, correspond to inputs that satisfy the decision problem's criteria.

A decision problem A is called decidable or effectively solvable if the formalized set of A is a recursive set. Otherwise, A is called undecidable. A problem is called partially decidable, semi-decidable, solvable, or provable if A is a recursively enumerable set.^{[nb 1]}