Recursively Enumerable Set
المؤلف:
Davis, M
المصدر:
Computability and Unsolvability. New York: Dover 1982.
الجزء والصفحة:
...
20-1-2022
1202
Recursively Enumerable Set
A set 
of integers is said to be recursively enumerable if it constitutes the range of a recursive function, i.e., if there exists a recursive function that can eventually generate any element in 
(Wolfram 2002, p. 1138). Any recursive set is also recursively enumerable.
The union and intersection of two recursively enumerable sets are also recursively enumerable.
Recursively undecidable problems give examples of recursively enumerable sets that are not recursive. For example, convergence of 
is known to be recursively undecidable, where 
denotes the Turing machine with Gödel number 
. Hence the set of all 
for which 
is convergent is not recursive. However, this set is recursively enumerable because it is the range of 
defined as follows:
![f(x)=<span style=]() {x if phi_x(x) is convergent; divergent if phi_x(x) is divergent. " src="https://mathworld.wolfram.com/images/equations/RecursivelyEnumerableSet/NumberedEquation1.svg" style="height:53px; width:283px" /> |
(1)
|
A set 
is recursive iff both 
and its complement are recursively enumerable. This provides an approach to constructing additional sets that are not recursively enumerable. In particular, the set of all Gödel numbers of total Turing machines is an example of a set which is not recursively enumerable.
The complements of recursively enumerable but not recursive sets are all not recursively enumerable, although complements of sets that are not recursively enumerable are not necessarily recursively enumerable. For instance, the complement of the set of all Gödel numbers of total Turing machines is not recursively enumerable.
One of fundamental properties of recursively enumerable sets is that they could be alternatively defined by domains as opposed to ranges. In particular, a set 
is recursively enumerable iff 
is the domain of a recursive function.
REFERENCES
Davis, M. Computability and Unsolvability. New York: Dover 1982.
Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.
Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1138, 2002.
الاكثر قراءة في المنطق
اخر الاخبار
اخبار العتبة العباسية المقدسة
