תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 52:
{{תזכורת|שימו לב: טענת '''אם״ם''' מוכיחים ע״י הוכחת שני הכיוונים: כיוון ה"אם" וכיוון ה"ורק אם"..}}
{{-}}
====דוגמה: רדוקציה מהשפה האוניברסלית לבעיית העצירה====
נראה כי
הוכח <math>L_U \le \text{HP}</math>.{{ש}}▼
[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות|השפה האוניברסלית]] <math>L_U</math> ניתנת לרדוקציה ל[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות|בעיית העצירה]]
נגדיר את הפונקציה <math>f(\langle M \rangle)=(\langle A \rangle,x)</math> כאשר <math>\langle A \rangle</math> היא קידוד של מ״ט שנבנית מתוך הקידוד של M באופן הבא: כל מעבר של M למצב <math>q_{rej}</math> מוחלף בלולאה אינסופית (למשל, ע״י מעבר למצב חדש q שתמיד עובר לעצמו, ללא תלות בקלט). נובע:▼
<math>HP</math>, כלומר
▲נגדיר את הפונקציה <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 נכנסת ללולאה:
** אם M לא עוצרת ← A לא עוצרת
| |||