שיחה:משפט רייס

לא ברור

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

אני מסכים לגבי הצורך להפריד בין אלגוריתם לתוכנית מחשב, אבל לא הייתי רוצה לוותר על הוכחה שבניסוח טוב כל אדם עם מעט ניסיון בתכנות (ואולי גם בלי) יוכל להבין ולהשתכנע בנכונותה. כדאי להוסיף הוכחה פורמלית למשפט עבור מכונת טיורינג, אבל לא הייתי מתייאש כל כך מהר שהניסיון לשכתב גם את ההוכחה הקיימת. חגי הלמן 23:06, 2 אוגוסט 2006 (IDT)

לולאה אינסופית

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

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

i=1;
while (i>0)
 i=i+1;

זאת על אף שהיא לא לולאה אינסופית לפי ההגדרה שלך (ראה גם את לולאה#לולאה אינסופית). בערך מטרת ההערה הייתה להבהיר למי שמגיע מתחום התכנות מתי אלגוריתם "לא עוצר" ע"י שימוש במושג שמוכר לו. אפשר לקצץ את המשפט עוד יותר ולמחוק בכלל את ההבהרה הזו. חגי הלמן 23:06, 2 אוגוסט 2006 (IDT)

אתה צודק כמובן, אבל צריך להבדיל בין הרעיון העקרוני של הלולאה ובין מה שיקרה בפועל. בפועל, על כל מחשב שעליו תריץ את התוכנה הזו, הלולאה תהיה דווקא מהסוג הראשון, כי מתישהו נחרוג מהגבול של המקום שמוקצה ל-i. גם אז לא מובטח שהלולאה תעצור (אם i הוא unsigned והתנאי הוא גדול שווה), אבל מובטח שנגיע לאותה "קונפיגורציה" שוב. אני מסכים שמבחינה קונספטואלית נראה שהלולאה הזו היא דווקא מהסוג הראשון, כי כדי להכניס ל-i ערכים הולכים וגדלים נצטרך יותר זיכרון. העניין הוא שהזיכרון עבור i בדרך כלל (בשפות התכנות שאני מכיר) הוא חסום מראש (ובתוך הלולאה לא עושים כלום כדי להגדיל אותו). בקיצור, שתי פנים לעסק. גדי אלכסנדרוביץ' 08:18, 3 אוגוסט 2006 (IDT)

משוב מ-14 בספטמבר 2018

כאן ניתן לכתוב משוב על הערך... הודעה זו נכתבה באמצעות מערכת המשוב. 
2001:4898:80E8:9:7C34:7FF8:81ED:6A8D 02:45, 15 בספטמבר 2018 (IDT) ±

הפונקציה הריקה בעלת התכונה

מה זה הניסוח הזה? אמור להיות לכאורה "הפונקציה הריקה בתכונה \ הפונקציה הריקה מוכלת בתכונה" וכדו'. תכונה היא אוסף פונקציות שהריקה יכולה להיות אחת מהן. הניסוח הבעייתי הזה מופיע בכמה מקומות --זה ינחמנו - שיחה 19:04, 8 בינואר 2019 (IST)

טעות שלי --זה ינחמנו - שיחה 18:32, 4 בפברואר 2019 (IST)