תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←התכנות בניית עץ השיוך: הרחבה |
←התכנות בניית עץ השיוך: עריכה |
||
שורה 195:
עפ"י ההגדרה,
<center><math>
min_{j \in J} |\Sigma|^{-(n_j(x) + 1)}
</math></center>
היות שאף תוכנית איננה מופיעה פעמיים באותה רמה בעץ, אז כל ה-<math>n_j</math> נפרדים. לכן נקבל:
שורה 201:
\forall_x \sum_{j \;|\; j \in J(x)}|\Sigma|^{-(n_j(x) + 1)}
\leq
\sum_{j = 0, 1, 2, \ldots}|\Sigma|^{
נפשט את הטור האינסופי:
<center><math>
\sum_{j = 0, 1, 2, \ldots}|\Sigma|^{
=
|\Sigma|^{
=
\frac{
\leq
.
</math></center>
|