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

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

החלט האם הבעיה הבאה היא כריעה: נתון ייצוג של מ״ט <math>M</math>. האם אפשר לבצע אופטימיזציה למכונה, כך לאחר האופטימיזציה, הזמןזמן הריצה שייקחשידרש עד קבלתלקבלת קלט <math>x</math> כלשהו יהיה קצר מאורך הקלט <math>|x|</math>?