דיון מעניין בפורום עתודה

[gil levi]

דיון מעניין בפורום עתודה

האם מח האדם הוא מכונת טיורינג? ואיך משפט אי השלמות מתקשר? זאת ועוד, בשרשור ה-זה!!!

 

[PooKiPsiT]

שאלה בקשר לבעיית העצירה

(הגעתי אליה אחרי שקראתי את השרשור הזה, ולכן החלטתי גם לשרשר את השאלה להודעה הזאת

) קראתי בויקיפדיה על בעיית העצירה, ויש שם משפט שאני לא מבינה: "היא מקבלת כקלט שם של תכנית ב' ובודקת האם תכנית ב' תעצור כאשר היא מקבלת כקלט את הקלט שקיבלה תכנית א'. אם התשובה היא "כן", תכנית א' תכנס ללולאה אינסופית ולא תעצור לעולם ואם התשובה היא "לא", היא תעצור מיד" למה אם תוכנית ב' עוצרת עבור קלט נתון, מכונה א' תכנס ללולאה אינסופית? ולמה אם תוכנית ב' לא עוצרת מכונה א' תעצר ישר?

 

[yossiea]

ההסבר בערך ככה...

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

 

[אולף]

זה שלב ביניים בהוכחה

לאחר *שתגדירי* מכונה שכזו (המכונה הזו היא מכונה שאת בעצמך מגדירה, זכותך להגדיר מכונה כזו, ותיכף תראי למה) תוכלי להריץ את המכונה הזו על עצמה, ותקבלי סתירה. כי אם מכונה א' תעצור על מכונה ב' (= מכונה א', כי אנו מריצים על עצמה) מכונה א' מוגדרת לא לעצור. אם מכונה א' לא תעצור על מכונה א', מכונה א' תעצור. שימי לב לסתירה שנוצרת כבר באופן מילולי - משהו עוצר אם ורק אם הוא לא עוצר. מכאן שאי אפשר להגדיר מכונה שבהינתן מכונה אחרת וקלט תוכל להכריע האם היא עוצרת או לא.

 

[inbal76]

קישור מומלץ

http://www.tzura.co.il/tshsd/yezira.asp?codyezira=10920 ההוכחה בשיר. חמוד ביותר.