תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←הגדרות: תקלדה |
מ ←הגדרות: הגהה |
||
שורה 13:
ה'''הסתברות האוניברסאלית''' של מחרוזת <math>x</math> היא
<center><math>
P_u(x) = \sum_{\langle M \rangle \;|\; M(\epsilon) = x} \left| \Sigma \right|^{- \left| \langle M \rangle \right|}.
</math></center>
}}
שורה 21:
עבור מחרוזת <math>x</math>, נניח ש-<math>M_K(x)</math> היא מ"ט בעלת התיאור הקצר ביותר המייצרת את <math>x</math>. אז '''הסתברות הקולמוגורוב''' של <math>x</math> היא
<center><math>
P_K(x) = \left| \Sigma \right|^{- \left| \langle M_K(x) \rangle \right|} = \left| \Sigma \right|^{- K(x)}.
</math></center>
}}
| |||