» נושאי לימוד
» נושאי לימוד
יום שישי 10 ביולי 2020
שאלות חזרה- המשך
דף ראשי  רדוקציות  שאלות חזרה- המשך גרסה להדפסה

      שאלות חזרה- המשך

 

 קבע האם השפה:

 {קיים קבוע Cp כך ש- P עוצרת על כל קלט תוך לא יותר  מ-Cp צעדים | P}= Hboun

ניתנת להכרעה?

 

פתרון:

טענה: Hbound  איננה ניתנת להכרעה.

הוכחה: ברדוקציה מ-H.

*Σ1={(P,w)|P is a program, w is a string} > H

*Σ2= {Q| Q is a program} > Hbound

 

נבנה רדוקציה f:Σ1*→Σ2* , כך שבהינתן זוג (P,w)  מוציאה

f(P,w)=Q, כך ש- (P,w) שייכת ל-H אמ"ם Q  שייכת ל-Hbound.

            Q(x)

              {

               P(w);

                Return;

              }

מתקיים:

אם P(w) עוצרת, אזי יהי d מספר הצעדים של P(w) עד לעצירה.

אזי לכל קלט x , Q(x) מבצעת d צעדים. כלומר Q שייכת ל- Hbound.

(עבור Cp=d)

אם P(w) לא עוצרת, אזי לכל קלט x, Q מבצעת אינסוף צעדים.

בפרט אין קבוע Cp כנדרש. כלומר Q לא שייכת ל- Hbound.

 

האם השפה:

{ p1 עוצרת על p2 אמ"ם p2 עוצרת על p1| (p1,p2)}=L4

ניתנת לקבלה?

 

פתרון:

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

הוכחה: רוצים p(w) לא עוצרת אמ"ם (p1,p2) שייך ל- L4.

               P1(x)

               {

                   p(w);

                }

 

               p2(x)

               {

                  while(1);

                }

p2 לא עוצרת על אף קלט, ובפרט גם לא על p1.

P1 לא עוצרת על אף קלט אם p(w) לא עוצרת.

אם p(w) עוצרת, אזי p1 עוצרת על כל קלט, בפרט על p2.

אבל p2 לא עוצרת על אף קלט, לכן (p1,p2) לא שייך ל- L4.

 

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