Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Computably enumerable set
Summary
In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable 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 simply a list of all the members of S: s1, s2, s3, ... . If S is infinite, this algorithm will run forever.
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 runs 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.
In computational complexity theory, the complexity class containing all computably enumerable sets is RE. In recursion theory, the lattice of c.e. sets under inclusion is denoted .
A set S of natural numbers is called computably enumerable 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.
The following are all equivalent properties of a set S of natural numbers:
Semidecidability:
The set S is computably enumerable. That is, S is the domain (co-range) of a partial computable function.
The set S is (referring to the arithmetical hierarchy).
There is a partial computable function f such that:
Enumerability:
The set S is the range of a partial computable function.
The set S is the range of a total computable function, or empty. If S is infinite, the function can be chosen to be injective.
The set S is the range of a primitive recursive function or empty. Even if S is infinite, repetition of values may be necessary in this case.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.