תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 22:
הרדוקציה, לכן, ממירה בעיה חדשה לבעיה קודמת שעליה אנו כבר יודעים משהו. בדוגמה זו, מצאנו דרך לפתור בעיה חדשה ע"י המרה לבעיה שפתרונה כבר קיים. אפשר לעשות גם הפוך: בהנתן בעיה, אפשר להראות שלו היה לה פתרון, אז היה גם פתרון לבעיה אחרת שלה ידוע שאין פתרון. בהמשך הפרק נשתמש ברעיון הרדוקציה כדי להמיר בין שפות פורמליות, בעיקר כדי להראות לגבי חלקן שהן אינן כריעות.
==רדוקציות בין שפות==
==הגדרה==▼
[[קובץ: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 היא פונקציה מלאה.
שורה 30 ⟵ 32:
נאמר ששפה <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>.
{{-}}
שורה 37 ⟵ 40:
נראה כי
[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות|שפת האלכסון]] <math>L_D</math> ניתנת לרדוקציה ל[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות|שפה האוניברסלית]]
<math>L_U</math>
<math>L_D \le L_U</math>.
נגדיר את פונקצית הרדוקציה <math>f(\langle M \rangle) = (\langle M \rangle,\langle M \rangle) </math>. נוכיח כי זו רדוקציה בהתאם להגדרה:
| |||