תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←דוגמאות ליישומי משפט רייס: עיצוב |
←משפט רייס: התרגיל הוא להוכיח, אבל המשפט שימושי להמשך ועל כן עדיף שיהיה כאן. |
||
שורה 67:
כלומר <math>\overline {L_S} \notin R</math>, ומכיוון ש־R סגורה למשלים, זו הוכחה ש־<math>L_S \notin R</math> כנדרש.
}}
למשפט רייס קיימת גם גרסא מורחבת:
{{משפט|שם=משפט רייס המורחב|תוכן=
לכל תכונה לא טריוויאלית S של שפות ב־RE מתקיים:{{רווח קשיח|10}} <math>L_S \notin RE</math>{{רווח קשיח|10}}}}
==דוגמאות ליישומי משפט רייס==
| |||