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

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

==שיטת ההוכחה==

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

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