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

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