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