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

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