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

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