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

# 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>.

 

 

נראה כי

[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות בRE|שפת האלכסון]] <math>L_D</math> ניתנת לרדוקציה ל[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות בRE|שפה האוניברסלית]]

{{תזכורת|שימו לב: טענת '''אם״ם''' מוכיחים ע״י הוכחת שני הכיוונים: כיוון ה"אם" וכיוון ה"ורק אם"..}}

{{-}}

נראה כי

[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות בRE|השפה האוניברסלית]] <math>L_U</math> ניתנת לרדוקציה ל[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות בRE|בעיית העצירה]]

 

נגדיר את הפונקציה <math>f(\langle M \rangle, x)=(\langle A \rangle,x)</math> כאשר <math>\langle A \rangle</math> היא קידוד של מ״ט שנבנית מתוך הקידוד של M באופן הבא: כל מעבר של M למצב <math>q_{rej}</math> מוחלף בלולאה אינסופית (למשל, ע״י מעבר למצב חדש q שתמיד עובר לעצמו, ללא תלות בקלט). נובע:

** אם M דוחה ← A לא עוצרת

** אם M מקבלת ← A מקבלת

*משני אלו נובעת התקפות של הרדוקציה. קל לראות שזו פונקציה מלאה וניתנת לחישוב ע״י מ״ט (כל שהמכונה נדרשת לעשות הוא החלפת הקידוד של מעבר ל־<math>q_{rej}</math> במעבר אחר).

 

==תכונות בסיסיות של רדוקציות==