בתשובה לאלון עמית, 23/02/04 20:52
התיזה של צ'רץ'-טיורינג 281720
יזהר • בתשובה לאלון עמית יום ג', 15/2/2005, 16:23
סליחה שאני מתערב, וסליחה על האורך, אבל יש קשר ישיר.
אפשר להוכיח את משפט גדל על ידי משפט אי העצירה. ההוכחה נוסחה על ידי טיורינג עצמו.

הרעיון בנפנוף ידיים, הוא כדלקמן:
קיימת פונקציה חד חד ערכית מאוסף כל מכונות הטיורינג למספרים הטבעיים. (לא זוכר אותה, אבל היא קיימת ומנוסחת היטב. תאמינו לי).

קיימת פונקציה בין מצבים שונים של מכונת טיורינג לבין המספרים הטבעיים. בינהם - מצב העצירה.

קיימת פונקציה בין כל הקלטים של מכונת טיורינג לבין המספרים הטבעיים.

מכל הטררם הנ"ל יוצא, שהמשפט "מכונת טיוריג M עוצרת מתישהו כשהיא מקבלת פלט T" הוא פסוק בתורת המספרים. שוב, זה קצת נפנוף ידיים, אבל זה הרעיון. גם המשפט ההפוך, "המכונה M אינה עוצרת לעולם כשהיא מקבלת פלט T" הוא פסוק בתורת המספרים

עכשיו בא הקטע המגניב באמת:

1)קיימת תוכנת מחשב Ma, שכידוע שקולה למכונת טיורינג, שמקבלת טקסט באנגלית, ומחליטה האם הטקסט הנ"ל הוא הוכחה תקנית (באמת כתבו אותה!) - כלומר - האם הטקסט מורכב מאקסיומות בהתחלה, משפט בסוף, וקשרים לוגיים נכונים בין כל משפט למשפטים הקודמים לו.

2) קיימת תוכנת מחשב Mb, שמייצרת את כל הטקסטים הסופיים, אחד אחרי השני (היא עובדת המון, אבל כל טקסט סופי, יבוא יומו והיא תייצר אותו)

3) נתן לMb לעבוד, ולשלוח טקסטים לMa, שתבדוק האם הטקסט הוא הוכחה תקנית.

4) נוסיף לMa שורות שיבדקו, במקרה שהיא מצאה שטקסט מסויים הוא הוכחה, האם האקסיומות שלו הם של תורת המספרים, והמשפט הסופי הוא "M עוצרת על T"

5) נוסיף עוד שורות שיבדקו מייד לאחר מכן, האם האקסיומות שלו הם של תורת המספרים, והמשפט הסופי הוא "M *לא* עוצרת על T"

אם לכל הפסוקים בתורת המספרים, או לשלילתם, היתה הוכחה,
אזי תוכנת המחשב (מכונת טיורינג) שבנינו הייתה מכריעה את בעיית העצירה.

כיון שאי אפשר להכריע את בעיית העצירה, אזי משפט גדל נכון.

חמוד, לא?
התיזה של צ'רץ'-טיורינג 282034
ירדן ניר-מפרגן • בתשובה ליזהר יום ה', 17/2/2005, 11:45
כן.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות