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

 

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

 

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