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

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