לכסון (שיטת הוכחה) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט: מעביר קישורי בינויקי לויקינתונים - d:q2904195 |
|||
שורה 22:
לצורך ההוכחה מסתמכים על כך שניתן למנות את כל האלגוריתמים בעולם, כך שבמניה זו יהיו כלולים כל האלגוריתמים. יש להדגיש כי כאן אנו עוסקים באלגוריתמים שמחזירים "כן" או "לא" בלבד, או שאינם עוצרים כלל (כלומר נכנסים ל[[לולאה]] אין סופית). לעתים נשתמש במניה שמכילה את כל האלגוריתמים של מחלקת [[סיבוכיות]] מסוימת, ולא של כל האלגוריתמים כולם.
מכיוון שקיימת מניה כזו (במסגרת זו לא נסביר כיצד), הרי שכל אלגוריתם יכול לקבל כ[[קלט]] את עצמו
כעת, נתאר לעצמנו טבלה בעלת אורך אין סופי ורוחב אין סופי. כל שורה בטבלה מכילה מידע על אלגוריתם אחד מתוך האלגוריתמים שבמניה. כל עמודה מכילה מידע על קלט אחד, כאשר הקלטים הם המספרים 0 עד אין-סוף.
| |||