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

פתרון אפשרי הוא ראשית למיין את הרשימה, ואז לבצע סריקה על הרשימה הממוינת לאיתור שני מספרים עוקבים זהים. כלומר, ראשית אנו '''ממירים''' את הקלט לקלט אחר (רשימה ממוינת), ואח"כ אנחנו '''פותרים בעיה קלה''' בהרבה – מציאת שני מספרים זהים ברשימה ממויינת.

 

#לכל קלט יש קלט מומר – ניתן להמיר כל קלט!

#ניתן לבצע את ההמרה ע״י מ״ט – ההמרה ברת־חישוב.

 

כעת נממש את הרעיון לעיל על שפות פורמליות.

==הגדרה==

תהיינה <math>L_1, L_2</math> שפות מעל א"ב <math>\Sigma</math>. הפונקציה <math>f: \Sigma^* \to \Sigma^*</math> נקראת '''רדוקציה''' מ־<math>L_1</math> ל־<math>L_2</math> אם מתקיים: