הועלה לאתר:  
מספר עמודים: 32
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת החישוביות - חלק ראשון

סיכום מאת: ניר אדר

6.3. תמונת העולם

עמוד זה לקוח מסיכום שנכתב על ידי Psibeast בנושא חישוביות.

מרחב השפות: (כולן מעל א"ב {0,1})




ריכוז שפות:

בעיית העצירה/שפת העצירה (Halting Problem):     {M עוצרת על X | <M>,<X>}=HP

השפה האוניברסלית:                                            {M מקבלת את X | <M>,<X>}=Lu

שפת האלכסון - כל המכונות המקבלות את הקידוד של עצמן:
{M מקבלת בריצתה את המחרוזת <M> | <M>}=LD

plot:[egin{gathered}   {L_{{Sigma ^*}}} = {  < M > |L(M) = {Sigma ^*}}  hfill \   {L_varepsilon } = {  < M > |varepsilon  in L(M)}  hfill \   {L_emptyset } = {  < M > |L(M) = emptyset }  hfill \   {L_{EQ}} = { ( < {M_1} > , < {M_2} > )|L({M_1}) = L({M_2})}  hfill \   {L_{ leqslant 3}} = {  < M > :|L(M)| leqslant 3}  hfill \   {L_{ = 3}} = {  < M > :|L(M)| = 3}  hfill \   {L_{ geqslant 3}} = {  < M > :|L(M)| geqslant 3}  hfill \ end{gathered} ]

כל המכונות המקבלות כל קלט:
כל המכונות אשר מקבלות את e:
כל המכונות אשר לא מקבלות אף קלט:
כל המכונות המקבלות אותם קלטים:
כל המכונות המקבלות 3 או פחות קלטים:
כל המכונות המקבלות בדיוק 3 קלטים:
כל המכונות המקבלות 3 קלטים או יותר:

תגיות המסמך:

לפרק הקודם6.2. משפט Rice
לפרק הבא6.3.1. תרגיל 1
מאת: דנה

החלק הראשון

בבקשה
מאת: אני

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299
מאת: רועי

אני חייב את המסמך הזה...הצילו

מאת: חשוון

מתי המסמך יחזור?
שיתוף:
| עוד