PDA

צפה בגרסה המלאה : [דיון] הסבר לרדוקציה



abuksis12
06-06-2016, 00:07
שלום,
אני לא מצליח לרדת לשורש העניין ברדוקציה.
למשל נתונה לי
40633

אומרים
אם L מזוהה טיורינג (בת מניה) ולא כריעה אז L^R מזוהה טיורינג (בת מניה) ולא כריעה

אז עכשיו מוכיחים את זה בעזרת רדוקציה
מוכיחים ש L^R מזוהה טיורינג ע"י הרדוקציה L
40634

ויש צד שני שאותו נעזוב כרגע.
איך מוכיחים את הרדוקציה הזאת?
הבנתי שהפונקציה של הרדוקציה היא
f(x) = x^R
מה זה אומר?

ואשמח להסבר

תודה

גל_כהן
06-06-2016, 07:46
כאששר אתה עושה רדוקציה משפה A לשפה B, אזי למעשה אתה מגדיר פונקציה חשיבה (כזו שבהינתן קלט כלשהו תוכל לחשב
את הפלט הנדרש) אשר עבורה $x\in A \iff f(x)\in B$. במקרה הזה, הפונקציה שלך תהיה $f(x)=x^R$, כלומר בהינתן מחרוזת x,
הפונקציה תחזיר את המחרוזת ההפוכה. כעת, f היא חשיבה ומובן ש-$x\in L\iff x^R\in L^R$, אזי זוהי רדוקציה כנדרש.

abuksis12
06-06-2016, 10:50
כאששר אתה עושה רדוקציה משפה A לשפה B, אזי למעשה אתה מגדיר פונקציה חשיבה (כזו שבהינתן קלט כלשהו תוכל לחשב
את הפלט הנדרש) אשר עבורה $x\in A \iff f(x)\in B$. במקרה הזה, הפונקציה שלך תהיה $f(x)=x^R$, כלומר בהינתן מחרוזת x,
הפונקציה תחזיר את המחרוזת ההפוכה. כעת, f היא חשיבה ומובן ש-$x\in L\iff x^R\in L^R$, אזי זוהי רדוקציה כנדרש.
אוקי תודה הבנתי,
אפשר לתאר את האלגוריתם של f(x) ככה? :

הרדוקציה:
בהינתן קלט <M,w> לשפה L^R נבנה קלט <N> לשפה L כך ש:
40636

N(x) :
- נפעיל את M על w
- אם w=x^R נעצור ונקבל
- אחרת נעצור ונדחה

אפשר ככה? (זה פשוט התבנית שלמדנו לרדוקציה)

avishay12456
10-06-2016, 09:26
קצת התבלבלת - מה שכתבת זה תבנית לרדוקציה כאשר השפות הן שפות של מכונות טיורינג עם תכונה כלשהי (למשל בעיית העצירה). במקרה הזה L היא שפה של מילים כלשהן מעל הא"ב שלך ולאו דווקא שפה של קידודי מכונות טיורינג.
הרדוקציה היא בדיוק מה שגל כתב מקודם - בהינתן קלט $x$ לשפה $L^R$ הפלט של הרדוקציה (שהוא בעצם קלט לשפה $L$) יהיה $x^R$.
בצורה יותר קצרה פונקציית הרדוקציה f מוגדרת להיות $f(x)=x^R$. ברור ש-f חשיבה ומקיימת את תנאי הרדוקציה $x\in L^R \Leftrightarrow f(x) \in L$.