Recursively enumerable set

A recursively enumerable set (also semi-decidable set , positive semi-decidable set , semi-decidable set , computable enumerable set , re , ce for short ) is a set of natural numbers in computability theory , if there is an algorithm that does the Enumerates elements of this set. This characterization is equivalent: There is an algorithm which outputs 1 whenever the input is an element of the relevant set and never stops on other inputs. Every decidable set is recursively enumerable, but there are recursively enumerable sets that are not decidable.

Sets of objects other than natural numbers are called recursively enumerable if they can be translated into a recursively enumerable set of natural numbers by Gödelization .

The term “ calculable set ” occasionally appears in the literature . This term is used inconsistently. It can mean decidable sets or recursively enumerable sets.

Formal definition

Formally, recursively enumerable sets are usually characterized by one of the following definitions that are equivalent to one another:

Recursive enumerability

A set is called recursively enumerable if is empty or if there is a total , computable function whose image is even . ${\displaystyle M\subseteq \mathbb {N} }$ ${\displaystyle M=\emptyset }$ ${\displaystyle \mathbb {N} \to M}$ ${\displaystyle M}$

Semi-decidability

The set is called semi-decidable if the partial characteristic function of is computable. ${\displaystyle M}$ ${\displaystyle \chi _{M}\colon \mathbb {N} \rightsquigarrow \{1\}}$ ${\displaystyle M}$

Equivalences to the definition

The following sentences are equivalent to one another:

• ${\displaystyle M}$ is recursively enumerable.
• ${\displaystyle M}$ is semi-decidable.
• ${\displaystyle M}$is of the Chomsky type 0 .
• ${\displaystyle M}$is the set of all calculation results of a Turing machine .
• ${\displaystyle M}$is the domain of a computable function.
• ${\displaystyle M}$is the image set of a computable function.
• ${\displaystyle M}$ is finite or the range of values ​​of an injective computable function.
• ${\displaystyle M}$is the image set of a primitive recursive function or the empty set.
• ${\displaystyle M}$is in the class of the arithmetic hierarchy . ${\displaystyle \Sigma _{1}^{0}}$
• ${\displaystyle M}$many-one can be reduced to the holding problem .
• There is a decidable amount which: . ${\displaystyle B\subseteq \mathbb {N} ^{2}}$ ${\displaystyle x\in M\Leftrightarrow \exists y\colon (x;y)\in B}$

properties

• Every decidable set is recursively enumerable, but there are recursively enumerable sets that are not decidable.
• A set is decidable if and only if it and its complement can be enumerated recursively.
• Every finite set can be enumerated recursively.
• Every recursively enumerable set is enumerable , but not all enumerable sets are recursively enumerable.
• Every infinite recursively enumerable set has subsets that are not recursively enumerable.
• The intersection of finitely many recursively enumerable sets is recursively enumerable; the union of a recursively enumerable set of recursively enumerable sets is recursively enumerable. There are recursively enumerable sets whose complement is not recursively enumerable.
• A partial function is computable if and only if its graph can be enumerated recursively.

Examples

• The set of pairs of the form: (program, input) with the property: the program stops with the input is recursively enumerable. This set is also called "Universal Language". The stopping problem of the Turing machines is thus semi-decidable, because the given Turing machine can be run with the given input and output 1 after it has been terminated . The complement of the holding problem is not semi-decidable.
• The self-applicability can be enumerated recursively: In the above example we limit ourselves to the inputs that correspond to the respective program.
• The equivalence problem of the Turing machines is not semi-decidable. The complement of the equivalence problem is also not semi-decidable.
• The values ​​of the busy beaver function cannot be recursively enumerated.

literature

• Hartley Rogers: Theory of recursive functions and effective computability . McGraw-Hill, 1967.