Rice's Theorem

---

If  is a class of recursively enumerable sets, then the set of Gödel numbers of functions whose domains belong to  is called its index set. If the index set of  is a recursive set, then either  is empty or  contains all recursively enumerable sets.

Rice's theorem is an important result for computer science because it sets up boundaries for research in that area. It basically states that only trivial properties of programs are algorithmically decidable.

---

REFERENCES

Davis, M. Computability and Unsolvability. New York: Dover, 1982.

Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.

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. 1137, 2002.

اخر الاخبار

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

مؤتمر السيد المجاهد يشهد عرض فيلم وثائقي عن سيرته العلمية ومشروع إحياء تراثه

بحث حوزوي يتناول التمييز بين المعجزة والسحر عند السيد المجاهد

بحث يناقش أثر القواعد العقلية في استنباط الأحكام الشرعية عند السيد محمد المجاهد

بحث علمي يناقش ردود السيد المجاهد على اللغويين والنحويين في كتابه (مفاتيح الأصول)

المزيد

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

هل توقيت نشاطك اليومي يؤثر على صحة دماغك؟.. العلماء يجيبون

"مشروب محبوب" يخفي فوائد لا يعرفها كثيرون

طبيب يكشف 5 أنواع للسعال.. بعضها خطير

نقص فيتامينات "خفي".. قد يفسّر التعب والتنميل وقلة التركيز

المزيد

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

دراسة: تغيّرات في أسلوب القيادة قد تكشف مبكرا عن الخرف !

عمرها 773 ألف سنة.. اكتشاف أقدم أحافير بشرية في المغرب

"اختراق علمي".. اختبار دم في منزلك قد يكشف ألزهايمر

ماذا يحدث للجسم عند قطع الكافيين فجأة؟

المزيد

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

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