שיחה:בעיית העצירה

ניסוח מחדש של ההוכחה

ההוכחה במתכונתה הקודמת נראתה לי "מתמטית" מדי - קצרה, תמציתית ובעיקר נותנת לקורא להבין בעצמו למה הרוב נכון. ניסיתי קצת להקהות את זה, בתקווה שהדבר משפר את הקריאות. כדי לשפוט אם הצלחתי צריך לשאול את דעתם של כמה הדיוטות. גדי אלכסנדרוביץ' 14:43, 8 בדצמבר 2006 (IST)

שיפור משמעותי לטעמי, אם כי אני לא הדיוט בתחום זה :-) רנדום 14:49, 8 בדצמבר 2006 (IST)

הקלט של Halt בשימוש בה כדי להגדיר את A הוא פעמיים התוכנית Q? זה לא אמור להיות תוכנית וקלט? יאיר ח. 14:55, 8 בדצמבר 2006 (IST)

זה (אחד) מהדברים המבריקים בהוכחה - מעבירים את התוכנית עצמה בתור "קלט". השאלה שלך מראה שיש מקום להרחבה בעניין בגוף הערך עצמו. גדי אלכסנדרוביץ' 15:19, 8 בדצמבר 2006 (IST)

כלומר, מתייחסים ל-Halt כפונקציה רקורסיבית שמקבלת שני מספרים טבעיים - האינדקס של התוכנית Q והקלט X? יאיר ח. 15:21, 8 בדצמבר 2006 (IST)

אוקיי, הבנתי. יאיר ח. 15:23, 8 בדצמבר 2006 (IST)

הסיבה?

הבעיתיות נובעת מהעובדה הבסיסית שאלגוריתם שאינו עוצר לעולם, אינו עוצר לעולם. ובשביל לבדוק זאת (בלי מעקב לוגי אחרי הלאגוריתם) נצטרך לחכות שהאלגוריתם יסיים (או לא יסיים) בשביל לדעת שהוא עצר (או לא עצר). לבן אדם יש את היכולת לגלות זאת, אבל לא ע"י בדיקה אלא ע"י הבנה של האלגוריתם כמובן. זה בגלל שלבן אדם יש את היכולת לזהות מגמתיות, ולחזות מראש שינוים במגמתיות. (כמו שאני יכול להגיד שהערכים של הפונקציה Y=X עולים ועולים בצורה אינסופית, וכמו שאני יכול לזהות שרקורסיה, גם אם תהיה מאד מורכבת, תעצור כשערך מסויים יהיה אפס) נכון, יכול להיות שאני טועה, אבל יש לי על מה לבסס את ההחלטה. אם נלמד מחשב לזהות מגמתיות, וחיזוי מראש של התנהגות של פונקציות ואלגוריתמים אז הוא יוכל לפתור את הבעיה. כמובן שהבעיה כאן היא שוב שאלגוריתם שמסוגל להבין ולנתח כל אלגוריתם הוא בעל סיבוכיות אינסופית. בני אדם מסוגלים לעשות זאת רק מתוקף היכולת שלנו ללמוד, ומוגבלים ע"י ההיקף של אותה יכולת. מגבלה שהיא פיסית בלבד, ולדעתי, ניתנת לפתירה בעולם דמיוני בו מימשו בינה מלאכותית לומדת על מחשב קוונטים (או כל מחשב בעל יכולת חישוב אינסופית).--84.229.57.35 15:59, 8 בדצמבר 2007 (IST)

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

מעניין לדעת איך זה מתקשר לנושא משפטי אי השלמות. מישהו? Gran - שיחה 08:19, 26 בספטמבר 2009 (IDT)

מה שתואר כאן אינו הבעייתיות, אלא רק הבעייתיות של ה"פתרון" הנאיבי לבעית העצירה. הגישה שאתה מציג - שהאדם אינו אלא אלגוריתם משוכלל ממילא, ולכן אם הוא מצליח לפתור את בעיית העצירה, גם מכונת טיורינג תוכל - סבירה יותר. בכל הנוגע למשפטי אי השלמות הקשר המרכזי ביותר הוא של השראה - טיורינג הכיר את משפט גדל, השתמש ברעיון הפניה-עצמית וקידוד-עצמי דומים לאלו של משפט גדל והוכיח מסקנת "אי אפשר" המזכירה במשהו את זו של גדל. עם זאת צריך להפריד בין השניים - גדל מדבר על כך שבמערכות הוכחה מסויימות יהיו קיימות טענות שניתנות לניסוח בידי המערכת אבל לא להוכחה/הפרכה בתוכה. טיורינג מדבר על כך שעבור מודל סביר וכללי של חישוב יהיו בעיות חישוביות שאותן המודל אינו מסוגל להכריע (למעשה, שיקולי ספירה פשוטים כבר מראים זאת - החשיבות של בעית העצירה בכך שהיא בעיה קונקרטית ומציאותית, וניתן להשתמש בה כדי להוכיח אי כריעות של בעיות קונקרטיות אחרות). גדי אלכסנדרוביץ' - שיחה 23:46, 28 בספטמבר 2009 (IST)

שאלה לי

אני מבין שהאלגוריתם Halt יכול להשתמש ב-Q גם כתוכנית וגם כקלט. אני לא מבין למה.

מה יהרס בהוכחה אם בתוכנית A נחליף את השורה Halt(Q,Q) בשורה Halt(Q,0) (או כל קלט אחר שבעולם)? ענק עדין - שיחה 01:43, 3 בספטמבר 2008 (IDT)

זו הדרך להריץ את A על עצמה. אם מחליפים את השורה Halt(Q,Q) בהגדרת A ב- Halt(Q,C), כאשר C קלט קבוע, אז יש שתי אפשרויות: אם Halt(A,C) (כלומר, A עוצרת על הקלט C), אז לפי הגדרת A, היא לא תעצור על הקלט A; מצד שני, אם A לא עוצרת על הקלט C, אז היא כן תעצור על הקלט A. בקיצור, A עוצרת על בדיוק אחד משני הקלטים A ו- C. בשלב הזה אין הרבה מה לומר, חוץ מ"אז מה". אבל אם מחליפים את C במשתנה Q (ולכן בערך A במקרה שלנו), נקבל ש-A עוצרת על A או על A, אבל לא על שניהם - וזו כמובן סתירה. עוזי ו. - שיחה 01:53, 3 בספטמבר 2008 (IDT)

מעניין לציין

שאם מסע בזמן היה אפשרי, אזי היה אפשר לפתור את בעיית העצירה. הנה האלגוריתם (A - האלגוריתם, I - הקלט):

1. הגדר משתנה X ואתחל אותו ל-0
2. חכה מספיק זמן שבו X יכול להשתנות.
3. אם X הוא 0,
   1. פלט "לולאה אינסופית"
4. אחרת,
   1. פלט "האלגוריתם עוצר"
5. בצא את A בקלט I
6. חזור אחורה בזמן למתי שבוצא שלב 2, ובמהלכו שנה את X ל-1

---כרוז • שיחה • חידות 15:16, 13 במרץ 2009 (IST)

זה לא יעבוד, כי אין לנו הגדרה ל"מספיק זמן" (אולי צריך יותר? (ואולי עוד יותר?)). 63.218.53.73 09:27, 4 בינואר 2012 (IST)

בעיות פתוחות במדעי המחשב

נראה לי שכדאי להוסיף קטגוריה של בעיות פתוחות במדעי המחשב, לדוגמה בעיית העצירה, P=NP וכו'. וגם לכתוב משהו על הפרסים הכספיים המוצעים למי שיפתור בעיות כאלה. משתמש:אנונימי 51 - שיחה 21:38, 25 באוגוסט 2010 (IDT)

אבל זו לא בעיה פתוחה; טיורינג הוכיח שאי אפשר, וזהו; הבעיה סגורה. 63.218.53.73 09:27, 4 בינואר 2012 (IST)

בעיית העצירה על מחשב בעל זיכרון סופי

הוספתי - בעיית העצירה על מחשב בעל זיכרון סופי. משתמש:אנונימי 51 - שיחה 22:56, 25 באוגוסט 2010 (IDT)