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:

{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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

أساتذة المجمَع العلمي يشرفون على تحكيم المسابقة القرآنية في جامعة النهرين

قسم الشؤون الدينية ينشر صناديق مخصصة لزكاة الفطرة داخل مرقد أبي الفضل العباس (عليه السلام) وخارجه

شعبة التوجيه الديني النسوي تختتم مجالسها العبادية لإحياء ليالي القدر المباركة

قسم الشؤون الفكرية ينظم ندوة توعوية ثقافية في محافظة ذي قار

المزيد

الآخبار الصحية

تأثير اللياقة البدنية على الدماغ

تجربة سريرية تظهر فوائد اللوز للمصابين بالسمنة

اكتشاف طريقة غير متوقعة لتقليل خطر الإصابة بالسكري

خمسة مؤشرات صحية مهملة قد تنقذ حياتك

المزيد

الآخبار التكنلوجية

علماء الجيولوجيا يفكون لغز الصدع العملاق تحت الماء في المحيط الأطلسي

تحذير جديد: الاحترار العالمي يتسارع وقد نكسر حاجز 1.5 درجة قبل 2030

الصين تكشف عن ألياف كربون تفوق قوة الفولاذ بـ10 مرات

الجهاز المناعي يظهر دورا غير متوقع في صحة العظام

المزيد

مواضيع ذات صلة

Lemma

Proof

Zeno,s Paradoxes

Unexpected Hanging Paradox

Strange Loop

Sorites Paradox

Simpson,s Paradox

Russell,s Antinomy

Paradox

Newcomb,s Paradox

Missing Dollar Paradox

Line Point Picking