משפט הריצוף

 

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

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

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

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

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

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

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

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

ההוכחה תהיה ברדוקציה הפוכה מ- 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)³ U (∑1×∑1×Q×∑1) U (∑1×Q×∑1×∑1) U ((∑1)³×Q)

U (∑1)² U (∑1×Q×∑1) U ((∑1)²×Q)

                           

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

 s3ε(∑1)³ U ((∑1 ×Q)× ∑1²) U (∑1×(∑1×Q)× ∑1) U (∑1²×(∑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).

 

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