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

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

לכאורה הבעיה עוסקת במכונה עצמה, אבל למעשה היא עוסקת בתכונה של השפה המתקבלת. כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה באופן הבא

S_P = \{ L |\mid L \in RE \bigwedge \exists_M \forall_x M \text{ accepts } x \text{ in less than } o( |x|) \text{ timesteps} \}.

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