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

<center> <math>L(M) \triangleq L_{acc}= \{ x\mid M(x) = \text{ accept}\}</math></center>

 

באופן דומה, ניתן להגדיר את השפה ה'''נדחית''' על ידי המכונה <math>L_{rej}(M)=\{ x \mid M(x)=\text{ reject} \}</math>. נדגיש כי לכל קלט ייתכנו שלושה מצבים: המכונה עצרה וקיבלה את הקלט, המכונה עצרה ודחתה את הקלט או המכונה לא עצרה. קלט ש"לא התקבל" על-ידי מכונה הוא קלט שנדחה או שהמכונה לא עצרה בעת החישוב. <math>L_\text{not accept}= \{ x\mid M(x)\ne\text{accept}\}</math>

{{-}}

 

===שקילות למודל הכללי ===