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

נתונה הבעיה: עבור רשימת מספרים הנתונה כקלט, מצא האם קיימים שנים מספרים זהים.

 

 

לא כל המרה לבעיה אחרת תעזור לנו לפתרון הבעיה המקורית. כדי לפתור בשיטה זו נדרשות תכונות תכונות מסויימות מתהליך ההמרה:

# 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_U \le \text{HP}</math>.{{ש}}

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

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

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

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

* לכן, אם <math>(\langle M \rangle,x)\in L_U</math>, כלומר, M מקבלת את הקלט x אזי A מקבלת את הקלט x, ובפרט עוצרת עליו, ומתקיים <math> (\langle A \rangle,x)\in\text{HP} </math>.

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