הוכחה שקיימת לפחות תוכנת מחשב טריוויאלית אחת שלא יכולה להתקיים

ההוכחות המתמטיות היפות ביותר, כרך א '. 2, מקסימה קוטה.

המאמר של השבוע שעבר היה בנושא "האם כמה אינסופיות גדולים יותר מאחרים?" והטיעון של החזן האלכסוני. השבוע אני רוצה לשתף את אחת הבעיות האהובות עלי על מדעי המחשב.

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

הגדרת H, תוכנית המחשבים הבלתי אפשרית

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

לדוגמה,

היא תוכנית שמסכמת את שני המספרים שאתה נותן לה כקלט, ו,

היא תוכנית המשתמשת בתוכנית אחרת - P_add - כקלט, ומעבירה לתוכנית זו את שתי התשומות האחרות. הוא עושה את מה ש- P_add (a, b) עושה ומכפיל אותו.

כאשר תוכנית מתבצעת, היא יכולה להיתקע, לרוץ לנצח ולעולם לא להפיץ שום דבר, למשל, תוכנית P_sum שתמשיך לסכום כל המספרים הטבעיים תמשיך להוסיף מספרים טבעיים לנצח מבלי שתסיים לרוץ (כלומר תפסיק) ו מוציא את התוצאה.

כעת נניח שהיא קיימת תוכנית H (P, i) שלוקחת כקלט את רשימת ההוראות P של התוכנית P (i) ואני את הקלט של P (i), ומוציאה 1 אם P (i) עצרו בשלב מסוים ו -0 אם P (i) נתקע ורץ לנצח. במילים פשוטות,

מדוע רשימת ההוראות ההיגיון אינה יכולה להתקיים

בהתבסס על ההוכחה של אלן טיורינג בעיתון "על מספרים ניתנים לחישוב, עם בקשה ל- Entscheidungsproblem" -1937, נוכיח כי H אינו יכול להתקיים.

בהתבסס על ההנחה כי קיים H אנו בונים תוכנית X (P) שרצה לנצח אם ורק אם H (P, P) = 1 ועוצרים אם ורק אם H (P, P) = 0. במילים אחרות,

כעת אנו יכולים לשקול לתת ל- X (i) רשימת הוראות X משלה כקלט: X (X).

לכן X (X) רץ לנצח אם ורק אם H (X, X) = 1 ו- X (X) נעצרים אם ורק אם H (X, X) = 0. במילים אחרות,

יש לנו סתירה! הראינו על ידי Reductio ad absurdum כי H אינו יכול להתקיים מכיוון שקיומו מוביל למסקנות אבסורדיות.

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

הפניות, אלן טיורינג. "על מספרים ניתנים לחישוב, עם יישום ל- Entscheidungsproblem". 1937.

אני מקס קוטה, מייסד משותף של Relativty.com, אוזניות VR שעיצבתי מאפס, מתוכם פתחתי את הקוד ואת החומרה. עקוב אחרי בטוויטר @ maxcoutte.