» נושאי לימוד
» נושאי לימוד
יום שישי 10 ביולי 2020
מתכונים 3
דף ראשי  רדוקציות  מתכונים  מתכונים 3 גרסה להדפסה

מתכונים- 3

 

דוגמא: HÆ ={P|L(P)= Æ} לא ניתנת להכרעה.

טענה: HÆ לא ניתנת לקבלה.

הוכחה: }             קיים W שעבורו P(W)  עוצרת HÆ={P| Hany  =`

נבנה תוכנית ACCEPT_Hany(X)  שמקבלת את Hany כלומר בהינתן P, ACCEPT_Hany(P) עוצרת אם"ם PÎHany

ACCEPT_Hany(P)

}

CHOOSE W NON-DETRMINISTICALLY

P(W)

RETURN()

{

אם PÎHany אז קיים חישוב של ACCEPT_Hany(Wo) שעוצר החישוב שמוצא W=Wo. לעומת זאת אם  PÏHanyאז כל חישוב של ACCEPT_Hany(P) לא עוצר. כלומר השפה של ACCEPT_Hany היא בדיוק Hany כלומר Hany ניתנת לקבלה Ü HÆ לא ניתנת לקבלה

מ.ש.ל.

דוגמא: {ב- L(P) יש מילים באורך זוגי בלבדHeven ={P| 

טענה: Heven לא ניתנת לקבלה .

הוכחה: Heven  לא ניתנת להכרעה, נראה כי `Heven ניתנת לקבלה. נבנה תוכנית ACCEPT_`Heven  שמקבלת את `Heven.   L(P) קיים X באורך אי זוגי `Heven= { P |

 

ACCEPT_`Heven(P)

}

GUESS X SUCH THAT |X| ODD

P(X)

RETURN

{



אם PÎ`Heven     אז קיים Xo  כך ש P(Xo) עוצרת Xo באורך אי זוגי Ü קיים חישוב של ACCEPT_`Heven(P) שעוצר – החישוב שמוצא X=Xo לעומת זאת אם PÏ`Heven אז לכל X באורך אי זוגי P(X) לא עוצרת ולכן לא קיים חישוב של  ACCEPT_`Heven(P) שעוצר.

Ü ACCEPT_`Heven מקבלת את `Heven Ü Heven  לא ניתנת לקבלה

מ.ש.ל.                

 

יש שפות שלא הם ולא המשלים שלהן ניתנות לקבלה, בניגוד לשפות שראינו עד עכשיו שהם לא ניתנות לקבלה אבל השפה המשלימה ניתנת לקבלה.

דוגמא: B={(P1,P2)|  L(P1) Í L(P2)}

טענה: B לא ניתנת לקבלה.

הוכחה: נניח ש- B ניתנת לקבלה נראה כי HÆ ניתנת לקבלה. כלומר בשלילה נניח כי קיימת ACCEPT_B  שמקבלת את B נבנה HÆ  ACCEPT_ שמקבלת את HÆ.

HÆ(P) ACCEPT_ עוצרת אם"ם Î HÆ P.

נתון ACCEPT_B(P1,P2) עוצרת אם"ם   L(P1) Í L(P2)

f(P)

}

P1=P

P2=NO_STOP(X)

}

                                                          

   WHILE(1)

}

RETURN(P1,P2)

{

 

HÆ(P) ACCEPT_

}

(P1,P2)=f(P)

ACCEPT_B(P1,P2)

RETURN

{

 

ACCEPT_B(P1,P2)

}

.

.

.

{

אז אם Î HÆ P אזי L(P) Í L(NO_STOP) Ü  (P,NO_STOP)ÎB Ü ACCEPT_B(P, NO_STOP) תעצור Ü HÆ(P) ACCEPT_ תעצור.

אם Ï HÆ P אז L(P) Ë L(NO_STOP) Ü  (P,NO_STOP)ÏB Ü ACCEPT_B(P, NO_STOP) לא תעצור Ü HÆ(P) ACCEPT_ עוצרת אם"ם Î HÆ P

                                                                       מ.ש.ל.

 

HÆ(P) ACCEPT_ מקבלת את HÆ בסתירה Ü ACCEPT_B  לא קיימת.           מ.ש.ל.   

 

 27-01-04 / 10:51  עודכן ,  01-01-04 / 21:17  נוצר ע"י שמרית דויטש  בתאריך 
 מתכונים 2 - הקודםהבא - מתכונים 4 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 7