משפט רייס
ויקיפדיה האנציקלופדיה encyclopedia
משפט רייס (מאנגלית: Rice's theorem), הוא משפט מרכזי בתחום החישוביות, שעוסק ביכולת של אלגוריתמים לחקור אלגוריתמים אחרים. המשפט אומר שאין תוכנית מחשב שמקבלת כקלט תוכנית מחשב אחרת, ומכריעה האם הפונקציה שמחשבת תוכנית מחשב זו היא בעלת תכונה מסוימת "לא-טריוויאלית" או לא (כלומר, תכונות אשר מאפיינות חלק מהפונקציות שמחושבות בידי תוכנית מחשב, אך לא את כולן). יש לשים לב שהתכונה היא תכונה של הפונקציה, ולא של תוכנית המחשב עצמה. באופן אינטואיטיבי המשפט טוען שתוכנית מחשב אינה יכולה לדעת כמעט מאום על הפלטים של תוכניות מחשב הנתונות לה כקלט.
באופן פורמלי, שפת הקידודים למכונות הטיורינג, שהשפה שלהן ב-
היא שפה בלתי כריעה אם היא קבוצה לא-טריוויאלית של שפות.
בנוסף, אם מתקיים כי אזי השפה אינה כריעה למחצה.
הקבוצה תחשב טריוויאלית אם היא הקבוצה הריקה (אינה מכילה אף שפה), או קבוצת כלל השפות מזוהות טיורינג. הסימון מציין מחרוזת בינארית המהווה קידוד של מכונת טיורינג .