לכסון (שיטת הוכחה) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
מ בוט החלפות: דוגמה; מסוים; לעתים; |
||
שורה 11:
כבר בראשית בתפתחותם של [[מדעי המחשב]], הבינו ראשי תחום זה כי בנוסף לעבודת המחקר של מציאת [[אלגוריתם|אלגוריתמים]] יעילים לבעיות ספציפיות, יש גם לאפיין את היכולת, או המסוגלות, של מכונות חישוב לפתור בעיות. שאלות אלה הן בעיקר השאלה מה [[מחשב]] (כל מחשב) מסוגל לחשב, ומה לא (במילים אחרות, האם קיימות [[פונקציה|פונקציות]] שלא ניתנות לחישוב, וכיצד ניתן להוכיח זאת), וכן השאלה מהן הבעיות שלא ניתן לחשב בזמן סביר. שאלות אלה מטופלות בתחומי המחקר [[חישוביות]] ו[[סיבוכיות]].<br />
תוך כדי עיסוק במחקר זה, נוצר הצורך למצוא שיטת [[הוכחה]] שבה ניתן יהיה להוכיח כי קיימת בעיה כלשהי לא ניתנת לחישוב, או לחישוב בזמן סביר.<br />
הקושי בטיפול בשאלות מעין אלה הוא ברור: קל מאוד להראות שניתן לפתור בעיה
==שיטת ההוכחה==
הרעיון הכללי של השיטה הוא גם הרעיון שעומד בבסיס האלכסון של [[קנטור]].<br />
לצורך ההוכחה מסתמכים על כך שניתן למנות את כל האלגוריתמים בעולם, כך שבמניה זו יהיו כלולים כל האלגוריתמים. יש להדגיש כי כאן אנו עוסקים באלגוריתמים שמחזירים "כן" או "לא" בלבד, או שאינם עוצרים כלל (כלומר נכנסים ל[[לולאה]] אין סופית).
מכיוון שקיימת מניה כזו (במסגרת זו לא נסביר כיצד), הרי שכל אלגוריתם יכול לקבל כ[[קלט]] את עצמו, או מספר המתאים למיקומו במניה זו.<br />
כעת, נתאר לעצמנו טבלה בעלת אורך אין סופי ורוחב אין סופי. כל שורה בטבלה מכילה מידע על אלגוריתם אחד מתוך האלגוריתמים שבמניה. כל עמודה מכילה מידע על קלט אחד, כאשר הקלטים הם המספרים 0 עד אין-סוף.
שורה 21:
נשאל את עצמנו את השאלה: האם בכל האלגוריתמים שנמצאים במניה שלנו יש אחד שמחשב את הפונקציה החדשה? התשובה היא כמובן: לא.<br />
כי נניח שאלגוריתם מספר x מחשב פונקציה זו, אז בפרט מה הוא מחזיר על הקלט x? אם לפי הטבלה הוא מחזיר "כן", אז לפי בניית הפונקציה החדשה הוא מחזיר "לא", ולהיפך - משמע שאלגוריתם מספר x '''לא''' מחשב את הפונקציה החדשה!<br />
יש לציין כי
להשלמת ההוכחה, יש להראות כי מחלקה כלשהי '''כן''' מכילה את הפונקציה החדשה שבנינו, וכך להראות שיש פונקציה שקיימת במחלקה ה"חזקה" ולא במחלקה ה"חלשה".<br />
שורה 29:
==מגבלות==
ניתן להראות כי שיטת הלכסון לא יכולה לעזור בהוכחה שמחלקה אחת "חזקה" יותר ממחלקה אחרת, עבור מחלקות
כדי להראות מגבלה של שיטת הלכסון, משתמשים במודלים של חישוב עם [[אורקל]], ונושא זה חורג מתחום ערך זה.
|