משפט רייס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
עברות הערך תגיות: שוחזרה עריכה חזותית |
מ שוחזר מעריכות של 141.226.162.108 (שיחה) לעריכה האחרונה של אקסינו |
||
שורה 1:
'''משפט
באופן פורמלי, השפה <math display="block">L_S= \{ \langle M\rangle \mid L(M) \in S\}</math> היא שפה '''[[כריעות|בלתי כריעה]]''', אם <math>\ S</math> היא קבוצה '''לא-טריוויאלית''' של שפות.
שורה 29:
אלא שהפונקציה הריקה אינה בעלת התכונה <math>\ \overline{X}</math> (שכן הנחנו שהיא כן בעלת התכונה <math>\ X</math>) ולכן הגענו לסתירה לתוצאה שהוכחנו בסעיף הקודם - הראינו כיצד ניתן להכריע האם אלגוריתם <math>\ A</math> נתון מחשב פונקציה בעלת תכונה לא טריוויאלית שהפונקציה הריקה לא מקיימת.
==קישורים חיצוניים==
| |||