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

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