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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

לכסון (Diagonal lemma) היא שיטת הוכחה מתמטית.

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

רעיון ההוכחה הוא: משערים שמחלקה אחת "חזקה יותר" ממחלקה אחרת.

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

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

רקע[עריכת קוד מקור | עריכה]

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

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

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

שיטת ההוכחה[עריכת קוד מקור | עריכה]

הרעיון הכללי של השיטה הוא גם הרעיון שעומד בבסיס האלכסון של קנטור.

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

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

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

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

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

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

להשלמת ההוכחה, יש להראות כי מחלקה כלשהי כן מכילה את הפונקציה החדשה שבנינו, וכך להראות שיש פונקציה שקיימת במחלקה ה"חזקה" ולא במחלקה ה"חלשה".

שימושים[עריכת קוד מקור | עריכה]

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

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

מגבלות[עריכת קוד מקור | עריכה]

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

הדוגמה הידועה ביותר היא שלא ניתן להראות כ 'P\neqNP' באמצעות שיטה זו.

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]