*#הפניה [[האלכסון של קנטור]] ▼{{עריכה}}
'''לכסון''' (Diagonalization) היא שיטת [[הוכחה]] מתמטית.<br />
מבין התחומים שבהם משתמשים בשיטה זו, נסביר כאן רק את השימוש שנעשה בשיטה זו בתאוריה של [[מדעי המחשב]].<br />
ב[[מדעי המחשב]] משתמשים בשיטה זו כדי להראות שמחלקה כלשהי שונה ממחלקה אחרת, זאת על ידי שמראים שהמחלקה האחת מכילה ממש את המחלקה האחרת.<br />
רעיון ההוכחה הוא:<br />
משערים שמחלקה אחת "חזקה יותר" ממחלקה אחרת.<br />
מראים שקיימת פונקציה במחלקה ה"חזקה יותר" שיכולה לקבל כקלט כל פונקציה במחלקה ה"חלשה יותר" ולחשב אותה.<br />
מגדירים פונקציה דומה לפונקציה הנ"ל, כך שתמיד יהיה קיים קלט שבו התוצאה שלה תהיה שונה מתוצאת כל פונקציה במחלקה האחרת.
מכיוון שכך, הרי שקיימת פונקציה במחלקה "החזקה יותר" שלא נמצאת במחלקה "החלשה יותר" - ומכך שהמחלקה ה"חזקה יותר" מכילה ממש את המחלקה "החלשה יותר".
==רקע==
כבר בראשית בתפתחותם של [[מדעי המחשב]], הבינו ראשי תחום זה כי בנוסף לעבודת המחקר של מציאת [[אלגוריתם|אלגוריתמים]] יעילים לבעיות ספציפיות, יש גם לאפיין את היכולת, או המסוגלות, של מכונות חישוב לפתור בעיות. שאלות אלה הן בעיקר השאלה מה [[מחשב]] (כל מחשב) מסוגל לחשב, ומה לא (במילים אחרות, האם קיימות [[פונקציה|פונקציות]] שלא ניתנות לחישוב, וכיצד ניתן להוכיח זאת), וכן השאלה מהן הבעיות שלא ניתן לחשב בזמן סביר. שאלות אלה מטופלות בתחומי המחקר [[חישוביות]] ו[[סיבוכיות]].<br />
תוך כדי עיסוק במחקר זה, נוצר הצורך למצוא שיטת [[הוכחה]] שבה ניתן יהיה להוכיח כי קיימת בעיה כלשהי לא ניתנת לחישוב, או לחישוב בזמן סביר.<br />
הקושי בטיפול בשאלות מעין אלה הוא ברור: קל מאוד להראות שניתן לפתור בעיה מסוימת - וזאת על ידי הצגת [[אלגוריתם]] שפותר את הבעיה. אבל כיצד ניתן להוכיח שלא ניתן לפתור בעיה כלשהי? כיצד ניתן להוכיח שבכלל קיימת בעיה כזו?<br />
==שיטת ההוכחה==
הרעיון הכללי של השיטה הוא גם הרעיון שעומד בבסיס האלכסון של [[קנטור]].<br />
לצורך ההוכחה מסתמכים על כך שניתן למנות את כל האלגוריתמים בעולם, כך שבמניה זו יהיו כלולים כל האלגוריתמים. יש להדגיש כי כאן אנו עוסקים באלגוריתמים שמחזירים "כן" או "לא" בלבד, או שאינם עוצרים כלל (כלומר נכנסים ל[[לולאה]] אין סופית). לעתים נשתמש במניה שמכילה את כל האלגוריתמים של מחלקת [[סיבוכיות]] מסוימת, ולא של כל האלגוריתמים כולם.<br />
מכיוון שקיימת מניה כזו (במסגרת זו לא נסביר כיצד), הרי שכל אלגוריתם יכול לקבל כ[[קלט]] את עצמו, או מספר המתאים למיקומו במניה זו.<br />
כעת, נתאר לעצמנו טבלה בעלת אורך אין סופי ורוחב אין סופי. כל שורה בטבלה מכילה מידע על אלגוריתם אחד מתוך האלגוריתמים שבמניה. כל עמודה מכילה מידע על קלט אחד, כאשר הקלטים הם המספרים 0 עד אין-סוף.
כל תא בטבלה מציין מהו הערך המוחזר מן ה[[אלגוריתם]] המתאים לשורה של תא זה, כאשר הקלט הוא הקלט המתאים לעמודה של תא זה.<br />
נגדיר פונקציה חדשה: הערכים שהפונקציה מחזירה הם ההפך מן הערכים של האלכסון הראשי, כלומר: אם אלגוריתם מספר 0, מחזיר על קלט 0 את התשובה "כן", הפונקציה שלנו תחזיר "לא" ולהפך. אם אלגוריתם מספר 1 מחזיר על קלט 1 את התשובה "כן", הפונקציה שלנו תחזיר "לא", ולהיפך. וכן הלאה לכל הקלטים האפשריים.<br />
נשאל את עצמנו את השאלה: האם בכל האלגוריתמים שנמצאים במניה שלנו יש אחד שמחשב את הפונקציה החדשה? התשובה היא כמובן: לא.<br />
כי נניח שאלגוריתם מספר x מחשב פונקציה זו, אז בפרט מה הוא מחזיר על הקלט x? אם לפי הטבלה הוא מחזיר "כן", אז לפי בניית הפונקציה החדשה הוא מחזיר "לא", ולהיפך - משמע שאלגוריתם מספר x '''לא''' מחשב את הפונקציה החדשה!<br />
יש לציין כי לעתים נשתמש בערכי הטבלה כפי שתואר כאן, ולפעמים לא נתעניין בערך המוחזר אלא בשאלה האם האלגוריתם עוצר. הפונקציה החדשה תהיה '''מוגדרת''' על קלט x אם האלגוריתם מספר x '''לא עוצר''', ולהיפך.<br />
להשלמת ההוכחה, יש להראות כי מחלקה כלשהי '''כן''' מכילה את הפונקציה החדשה שבנינו, וכך להראות שיש פונקציה שקיימת במחלקה ה"חזקה" ולא במחלקה ה"חלשה".<br />
==שימושים==
באמצעות שיטת הלכסון ניתן להוכיח כי קיימות פונקציות שלא ניתנות לחישוב.<br />
כמו כן ניתן באמצעות שיטה זו להראות היררכיה של זמן והיררכיה של מקום.<br />
==מגבלות==
ניתן להראות כי שיטת הלכסון לא יכולה לעזור בהוכחה שמחלקה אחת "חזקה" יותר ממחלקה אחרת, עבור מחלקות מסוימות.<br />
הדוגמה הידועה ביותר היא שלא ניתן להראות כ 'P!=NP' באמצעות שיטה זו.<br />
כדי להראות מגבלה של שיטת הלכסון, משתמשים במודלים של חישוב עם [[אורקל (מדעי המחשב)|אורקל]], ונושא זה חורג מתחום ערך זה.
==ראו גם==
[[קטגוריה:הוכחה]]
[[ja:対角化]]
| 