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

בבפרק [[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות|קיום שפות לא כריעות]] ראינו שבעייהשבעיה ספיציפית, בעיית העצירה, איננה כריעה, וראינווכן ראינו משיקולי מניה שיש אינספור שפות שאינן אפילו כריעות למחצה. לעתים רוצים להוכיח קיום (או שלילת-קיום) רמת כריעות כלשהי של שפה כלשהי. במצב כזה, אין טעם "להוכיח את הגלגל מחדש" ולבנות סתירה כפי שעשינו ב[[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות#קיום שפות לא כריעות|הוכחת אי-כריעותה של בעיית העצירה]]. במקום זאת, כדאי לבנות על מה שכבר ידוע. נציג כאן את רעיון ה'''רדוקציה''' שהינו אחד הרעיונות המרכזיים ביותר במדעי המחשב. הרעיון שעומד מאחורי הרדוקציה הוא המרת בעיה אחת לבעיה קודמת, ידועה יותר.