משפט רייס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←הוכחת המשפט: clean up, replaced: [[תחום ההגדרה ← [[תחום של פונקציה#תחום ההגדרה |
שם נרדף למשפט, השימוש בשם זה מקובל יותר בחוגים עבריים. תגיות: שוחזרה עריכה חזותית |
||
שורה 1:
'''משפט רייס (משפט אורז)''' הוא [[משפט (מתמטיקה)|משפט]] מרכזי בתחום ה[[חישוביות]], שעוסק ביכולת של [[אלגוריתם|אלגוריתמים]] לחקור אלגוריתמים אחרים. המשפט אומר שאין [[תוכנית מחשב]] שמקבלת כקלט תוכנית מחשב אחרת, ומכריעה האם ה[[פונקציה]] שמחשבת תוכנית מחשב זו היא בעלת תכונה מסוימת "לא-טריוויאלית" או לא (כלומר, תכונות אשר מאפיינות חלק מהפונקציות שמחושבות בידי תוכנית מחשב, אך לא את כולן). יש לשים לב שהתכונה היא תכונה של הפונקציה, ולא של תוכנית המחשב עצמה. באופן אינטואיטיבי המשפט טוען שתוכנית מחשב אינה יכולה לדעת כמעט מאום על הפלטים של תוכניות מחשב הנתונות לה כקלט.
באופן פורמלי, השפה <math display="block">L_S= \{ \langle M\rangle \mid L(M) \in S\}</math> היא שפה '''[[כריעות|בלתי כריעה]]''', אם <math>\ S</math> היא קבוצה '''לא-טריוויאלית''' של שפות.
| |||