ויקיספר

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמת
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
←‏משפט הרדוקציה: תיקנתי שגיאה בסעיף משפט הרדוקציה
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד
אין תקציר עריכה
 
שורה 3:
בפרק [[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות|קיום שפות לא כריעות]] ראינו שבעיה ספיציפית, בעיית העצירה, איננה כריעה, וכן ראינו משיקולי מניה שיש אינספור שפות שאינן אפילו כריעות למחצה.
בהנתן שפה <math>L</math>, נוכל לשאול היכן היא ממוקמת בעולם השפות: האם היא כריעה, או כריעה למחצה, או אולי לא כריעה אפילו למחצה.
בפרק זה נציג טכניקה שמקלה את סיווג השפות למחלקות השונות. הטכניקה נקראת '''רדוקציה''' והיא אחתאחד הרעיונות המרכזיים ביותר במדעי המחשב. הרעיון שעומד מאחורי הרדוקציה הוא המרת בעיה נתונה לבעיה קודמת עבורה כבר ידוע הפתרון. שימוש בשיטה זו מונע את הצורך לבצע "הוכחה ישירה" על כל שפה (כפי שעשינו ב[[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות#קיום שפות לא כריעות|הוכחת אי-כריעותה של בעיית העצירה]]).
 
 
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/כריעות_שפות/רדוקציה_חישובית"