רדוקציה חישובית
מתוך ויקיפדיה, האנציקלופדיה החופשית
במדעי המחשב, רדוקציה חישובית בין פונקציה A לפונקציה B היא פונקציה f מלאה וניתנת לחישוב מקבוצת הקלטים האפשריים של A לקבוצת הקלטים האפשריים של B, כך שלכל x מתקיים: 
. אם קיימת רדוקציה כזו מ-A ל-B, נסמן זאת: 
.
אם ו-B ניתנת לחישוב, אזי גם A ניתנת לחישוב. ולהיפך: אם A לא ניתנת לחישוב, אזי גם B לא ניתנת לחישוב.
[עריכה] רדוקציה בין שפות
אם A ו-B הן פונקציות שמייצגות שפות, ומתקיים , אזי:
- אם A ניתנת להכרעה, גם B ניתנת להכרעה.
- אם קיימת מכונת טיורינג שמקבלת את A, אזי גם קיימת גם מכונת טיורינג שמקבלת את B.
.
