ויקיספר

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Atavory (שיחה | תרומות)
7,521 עריכות
Atavory (שיחה | תרומות)
7,521 עריכות
שורה 74:
 
 
3. '''בעייתשפת העצירה''', <math>M \}</math> עוצרת על <math>\text{HPH} = \{ (\langle M \rangle,x) \mid x</math>{{ש}}
:שייכות ל־RE: נריץ את M על x – אם המכונה תעצור, נקבל. אחרת – M לא עצרה וגם המכונה המסמלצת בלולאה אינסופית, ואינה מקבלת את הקלט הנ״ל.
 
 
מההגדרה, נובע עבור השפות המשלימות, <math>\overline{L_U}, \overline{L_D}, \overline{\text{HPH}} \in coRE</math>.
 
[[קטגוריה:תורת החישוביות]]
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/כריעות_שפות"