תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף

כצעד ראשון לקראת ההוכחה ששפות מסוימות אינן כריעות, נרצה להציג את רעיון ה'''רדוקציה''' שהינו אחד הרעיונות המרכזיים ביותר במדעי המחשב. הרעיון שעומד מאחורי הרדוקציה הוא פתרון בעיה מסוימת ע״י כלים ידועים. במילים אחרות, במקום לפתור את הבעיה עצמה, "נשנה" את הבעיה הנתונה לבעיה אחרת, אותה אנו יודעים כבר לפתור, ובאופן זה נפתור את הבעיה המקורית.

 

==מוטיבציה==

נתונה הבעיה: עבור רשימת מספרים הנתונה כקלט, מצא האם קיימים שנים מספרים זהים.