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

* היא חסרה לפחות שפה אחת: נניח שפה מהצורה <math>L= \{wb \mid w=w_1w_2\ldots w_k\in \Sigma^*, b\in\Sigma, \exsits_iexists i \ w_i=b\}</math>, כאשר <math>b</math> הוא תו כלשהו ו-<math>w</math> היא מחרוזת שאחת מהאותיות בה נדרשת להיות <math>b</math>. קל לראות שכל מ״ט המקבלת את השפה חייבת לקרוא את הקלט עד סופו, ולכן זמן ריצתה הוא לכל הפחות להיות <math>|x|</math>, ועל כן <math>L \notin S_P</math>.

לפי משפט רייס, בעיית ההכרעה של השפה <math>L_{S_P}</math> אינה בב־<math>R</math>, ובפרט, לא ניתן להכריע את השאלה האם ניתן לבצע אופטימיזציה כזו.