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