לכסון (שיטת הוכחה) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 17:
מכיוון שקיימת מניה כזו (במסגרת זו לא נסביר כיצד), הרי שכל אלגוריתם יכול לקבל כ[[קלט]] את עצמו, או מספר המתאים למיקומו במניה זו.<br />
כעת, נתאר לעצמנו טבלה בעלת אורך אין סופי ורוחב אין סופי. כל שורה בטבלה מכילה מידע על אלגוריתם אחד מתוך האלגוריתמים שבמניה. כל עמודה מכילה מידע על קלט אחד, כאשר הקלטים הם המספרים 0 עד אין-סוף.
כל תא בטבלה מציין מהו הערך המוחזר מן
נגדיר פונקציה חדשה: הערכים שהפונקציה מחזירה הם ההפך מן הערכים של האלכסון הראשי, כלומר: אם אלגוריתם מספר 0, מחזיר על קלט 0 את התשובה "כן", הפונקציה שלנו תחזיר "לא" ולהפך. אם אלגוריתם מספר 1 מחזיר על קלט 1 את התשובה "כן", הפונקציה שלנו תחזיר "לא", ולהיפך. וכן הלאה לכל הקלטים האפשריים.<br />
נשאל את עצמנו את השאלה: האם בכל האלגוריתמים שנמצאים במניה שלנו יש אחד שמחשב את הפונקציה החדשה? התשובה היא כמובן: לא.<br />
כי נניח שאלגוריתם מספר x מחשב פונקציה זו, אז בפרט מה הוא מחזיר על הקלט x? אם לפי הטבלה הוא מחזיר "כן", אז לפי בניית הפונקציה החדשה הוא מחזיר "לא", ולהיפך - משמע שאלגוריתם מספר x '''לא''' מחשב את הפונקציה החדשה!<br />
יש לציין כי לעיתים נשתמש בערכי הטבלה כפי שתואר כאן, ולפעמים לא נתעניין בערך המוחזר אלא בשאלה האם האלגוריתם עוצר. הפונקציה החדשה תהיה '''מוגדרת''' על קלט x אם האלגוריתם מספר x '''לא עוצר''', ולהיפך.<br />
להשלמת ההוכחה, יש להראות כי מחלקה כלשהי '''כן''' מכילה את הפונקציה החדשה שבנינו, וכך להראות שיש פונקציה שקיימת במחלקה ה"חזקה" ולא במחלקה ה"חלשה".<br />
==שימושים==
| |||