Recursively enumerable set

As a recursively enumerable set (also semi- decidable set, positive semi- decidable set, semi - decidable set, computable enumerable set, re short, ce ) is in computability theory a set of natural numbers called, if there is an algorithm that enumerates elements of this set. Equivalent is this characterization: There is an algorithm that outputs 1 whenever the input is element of the set in question, and never stops at other entries. Every decidable set is recursively enumerable, but there are recursively enumerable sets that are not decidable.

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

In the literature, appears occasionally on the notion of computable quantity. This term is used inconsistently. It can thus be meant decidable or recursively enumerable quantities quantities.

Formal definition

Formal enumerable sets are recursively usually by one of the following mutually equivalent, definitions characterized:

A lot of hot recursively enumerable if is empty or there is a total computable function whose image is straight.

The amount of hot semi- decidable if the partial characteristic function of is computable.

Equivalences for defining

The following sentences are equivalent to each other:

• Is recursively enumerable.
• Is semi- decidable.
• Is the Chomsky type 0
• Is the set of all calculation results of a Turing machine.
• Is domain of a computable function.
• Range of values ​​is a computable function.
• Is finite or value range of a computable injective function.
• Is value range of a primitive recursive function or the empty set.
• Is the class of the arithmetic hierarchy.
• Can be reduced many-one on the halting problem.
• There is a decidable amount in which:.

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 are recursively enumerable.
• Every finite set is recursively enumerable.
• Every recursively enumerable set is countable, but not all countable sets are recursively enumerable.
• Every infinite recursively enumerable set has subsets that are not recursive 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 is recursively enumerable.

Examples

• The set of pairs of the form ( program input ) with the property: the program stops with the input is recursively enumerable. This quantity is also called the "Universal Language". Thus, the halting problem of the Turing machine is semi- decidable, because you can leave the given Turing machine to run with the given input and output after its termination 1. The complement of the halting problem is semi- decidable.
• The self- applicability is recursively enumerable: In the example above we restrict ourselves to the entries that correspond to the respective program.
• The equivalence problem of Turing machines is not semi- decidable. Also, the complement of the equivalence problem is not semi- decidable.
• The values ​​of the Busy Beaver function are not recursively enumerable.