תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
מ עריכה - הורדת תבנית "בעבודה"
Atavory (שיחה | תרומות)
שורה 63:
==דוגמאות ליישומי משפט רייס==
 
משפט רייס מאפשר בצורה קלה מאד להוכיח שבעיות רבות אינן כריעות. אםעם זאת, יש להשתמש בו בזהירות. כפי שצויין ב[[#תכונות של שפות|תכונות של שפות]], למרות שהחלטת התכונה פורמאלית מופעלת על ייצוג של מ"ט, התכונה היא למעשה של שפות, ובפרט שפות נתנות למניה רקורסיבית. כדי להשתמש במשפט רייס, יש לתרגם את השאלה כך שהיא פועלת על שפות נתנות למניה רקורסיבית. להלן מספר דוגמאות נכונות ושגויות לשימוש במשפט רייס (ב[[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים|דף התרגילים]] אפשר למצוא דוגמאות נוספות).
 
{{דוגמה|תוכן=