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

     משפט הריצוף

 

משפט: T לא ניתנת להכרעה.

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

{p עוצרת על Israel | p}= Hisrael

נסתכל בשפה נוספת שההוכחה שלה מאוד דומה ל- Hisrael.

{p(ε) עוצרת | p }=.

אמרנו שתוכניות ומ"ט שקולות, לכן נגדיר שפה:

{M מ"ט, ו- M עוצרת על ε | M }=.

לא ניתנת להכרעה בדומה ל- .

ההוכחה תהיה ברדוקציה הפוכה מ- .

 

נרצה פונקציה g שמקבלת כקלט מ"ט M, M=(Q,∑,δ,s,h), ומוציאה כפלט

g(M)=A=(C,c0) כך של- A ריצוף תקין אמ"ם M לא עוצרת על ε.

 

טבלת המעברים של M: (לא עוצרת על אף קלט, ובפרט לא על ε.)

s,#,q,1

q,1,s,R

 

יש שתי אפשרויות: או ש-h יופיע באיזשהו שלב, ואז המכונה עוצרת על הקלט הריק, או ש-h לא יופיע ולא נעצור.

 

קבוצת סימנים:

S=(∑1)3 U (∑1×∑1×Q×∑1) U (∑1×Q×∑1×∑1) U ((∑1)3×Q)

U (∑1)2 U (∑1×Q×∑1) U ((∑1)2×Q)

                           

אריח C=(S1,S2,S3,S4) מקיים את התנאים הבאים:

 s3ε(∑1)3 U ((∑1 ×Q)× ∑12) U (∑1×(∑1×Q)× ∑1) U (∑12×(∑1×Q)

 

עבור: S3=(y1,y2,y3)

S2=(y2,y3)

S4=(y1,y2)

 

אפשרויות עבור S1 :

 

1)       אם y1,y2,y3ε∑1  אזי: S1=(y1',y2',y3')

יכול להיות  y1'=y1

Y2'=y2

Y3'=y3

 

2) אם y1,y2,y3ε∑1      y1'=y1       y2'=y2

y3'=(y3,q) עבור qεQ.

 

3) אם y1,y2,y3ε∑1  אזי יש אפשרות y3'=y3       y2'=y2

y1'=(y1,q) עבור qεQ

אם y1ε∑1,  y3ε∑1, y2=(π,q) ו- δ(q,π)=(p,σ), עבור σε∑, אזי: y1'=y1, Y3'=y3,

 y2'=(σ,p).

 

בצורה הזאת אפשר לכתוב את כל האפשרויות לאריחים שלנו.

 

 09-02-04 / 10:14  עודכן ,  21-01-04 / 11:33  נוצר ע"י שמרית דויטש  בתאריך 
 הגדרות - הקודםהבא - מסקנות 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 2