לכסון (שיטת הוכחה)

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

רקע

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

שיטת ההוכחה

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

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

שימושים

באמצעות שיטת הלכסון ניתן להוכיח כי קיימות פונקציות שלא ניתנות לחישוב.
כמו כן ניתן באמצעות שיטה זו להראות היררכיה של זמן והיררכיה של מקום.

מגבלות

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