לכסון (שיטת הוכחה) – הבדלי גרסאות

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

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

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

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

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