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

{{תורת החישוביות}}

 

 

<div class="toclimit-3">__TOC__</div>

{{-}}

 

 

נראה כי

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

{{-}}

נראה כי

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

*מצד שני כאשר <math>(\langle M \rangle,x)\notin L_U</math> אזי M או דוחה את x או לא עוצרת עליו. בשני המקרים A לא עוצרת על x ומתקיים <math> (\langle A \rangle,x)\notin\text{HP} </math>.

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

 

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

מכיוון ש־f פונקציה מלאה, חישוב <math>f(x)</math> יסתיים לכל קלט x, ומכיוון ש־<math>M_2</math> מכריעה (כלומר, עוצרת על כל קלט) גם המכונה <math>M_1</math> עוצרת לבסוף על כל קלט. כמו כן, f <u>תקפה</u>, כלומר <math>x\in L_1</math> אם״ם <math>f(x)\in L_2</math>. לכן אם <math>x\in L_1</math> אז הקלט המומר <math>f(x)\in L_2</math>, ו־<math>M_2</math> תקבל את הקלט. מכאן שבמקרה זה <math>M_1</math> מקבלת את x. מצד שני, אם <math>x\notin L_1</math> אזי <math>f(x)\notin L_2</math> ולכן <math>M_2</math> דוחה את הקלט המומר, וגם <math>M_1</math> דוחה כנדרש. מכאן נובע – <math>M_1</math> מכריעה את <math>L_1</math> ו־<math>L_1\in R</math> לפי ההגדרה.}}

 

 

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

הסבר: נניח ש־<math>L_1\notin R</math>. אם <math>L_2\in R</math> נובע ממשפט הרדוקציה שהוכחנו לעיל שגם <math>L_1\in R</math>, וזו סתירה.