תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←משפט הרדוקציה: הגהה |
מ תיקון קישור |
||
שורה 39:
נראה כי
[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות בRE|שפת האלכסון]] <math>L_D</math> ניתנת לרדוקציה ל[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות בRE|שפה האוניברסלית]]
<math>L_U</math>, כלומר
<math>L_D \le L_U</math>.
שורה 54:
===דוגמה: רדוקציה מהשפה האוניברסלית לבעיית העצירה===
נראה כי
[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות בRE|השפה האוניברסלית]] <math>L_U</math> ניתנת לרדוקציה ל[[תורת_החישוביות/כריעות_שפות#דוגמאות לשפות בRE|בעיית העצירה]]
<math>HP</math>, כלומר
<math>L_U \le HP</math>.
| |||