תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←הגדרה: הגהה, קישורים פנימיים |
|||
שורה 26:
[[קובץ:Reduction map.png|שמאל|ממוזער|200px|רדוקציה: כל הקלטים ב־<math>L_1</math> ממופים לקלטים של <math>L_2</math>, ואילו קלטים שאינם ב־<math>L_1</math> ממופים לקלטים שאינם ב־<math>L_2</math>]]
תהיינה <math>L_1, L_2</math> שפות מעל א"ב <math>\Sigma</math>. הפונקציה <math>f: \Sigma^* \to \Sigma^*</math> נקראת '''רדוקציה''' מ־<math>L_1</math> ל־<math>L_2</math> אם מתקיים:
# f היא פונקציה מלאה.
# f ניתנת לחישוב.
# הרדוקציה <u>תקפה</u>: <math>x\in L_1</math> אם״ם <math>f(x)\in L_2</math>.
נאמר ששפה <math>L_1</math> '''ניתנת לרדוקציה''' ל־<math>L_2</math> אם קיימת רדוקציה מ־<math>L_1</math> ל־<math>L_2</math>, ונסמן: <math>L_1 \le L_2</math>. המשמעות היא שניתן להמיר קלט עבור הבעיה <math>L_1</math> לקלט מתאים עבור השפה <math>L_2</math>. אם יש לנו "כלי" שמכריע את השפה <math>L_2</math>, אותו כלי יכול לשמש להכרעת <math>L_1</math>.
{{-}}
===דוגמה: רדוקציה משפת האלכסון לשפה האוניברסלית===
נראה כי
[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות|שפת האלכסון]] <math>L_D</math> ניתנת לרדוקציה ל[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות|שפה האוניברסלית]]
<math>L_U</math>.
נגדיר את פונקצית הרדוקציה <math>f(\langle M \rangle) = (\langle M \rangle,\langle M \rangle) </math>. נוכיח כי זו רדוקציה בהתאם להגדרה:
| |||