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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
מ הגהה
Atavory (שיחה | תרומות)
מ עריכה
שורה 1:
{{תורת החישוביות}}
{{בעבודה}}
 
 
כצעד ראשון לקראת ההוכחה ששפות מסוימות אינן כריעות, נרצה להציג את רעיון ה'''רדוקציה''' שהינו אחד הרעיונות המרכזיים ביותר במדעי המחשב. הרעיון שעומד מאחורי הרדוקציה הוא פתרון בעיה מסוימת ע״י כלים ידועים. במילים אחרות, במקום לפתור את הבעיה עצמה, "נשנה" את הבעיה הנתונה לבעיה אחרת, אותה אנו יודעים כבר לפתור, ובאופן זה נפתור את הבעיה המקורית.