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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
מ ←‏משפט הרדוקציה: הגהה, עיצוב
ShoobyD (שיחה | תרומות)
←‏דוגמא: תיקון
שורה 34:
#* אם <math>\langle M \rangle \in L_D</math> אזי מהגדרת <math>L_D</math> נובע ש־<math> \langle M \rangle \in L(M)</math>, כלומר המכונה M מקבלת את המחרוזת <math>\langle M \rangle</math>. מכאן נובע <math>(\langle M \rangle,\langle M \rangle)\in L_U</math> לפי הגדרת השפה <math>L_U</math>.
#* הכיוון השני מוכח באופן זהה:
<center><math>\langle M \rangle \notin L_D \Rightarrow \langle M \rangle \notin L_DL(M) \Rightarrow (\langle M \rangle,\langle M \rangle)\notin L_U</math></center>
{{תזכורת|שימו לב: טענת '''אם״ם''' מוכיחים ע״י הוכחת שני הכיוונים: כיוון ה"אם" וכיוון ה"ורק אם"..}}
{{-}}
שורה 47:
*מצד שני כאשר <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> במעבר אחר).
 
 
==תכונות הרדוקציה==