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