תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←התכנות בניית עץ השיוך: הרחבה |
|||
שורה 161:
====התכנות בניית עץ השיוך====
נניח
<math>|\langle M \rangle| + 1</math>. מהיכן אנו יודעים שהדבר נכון?
{{הוכחה|
נגדיר כ-<math>h</math> את אורך התוכנית הארוכה ביותר שהסתיימה בזמן ש-<math>M</math> הסתיימה (כולל <math>M</math> עצמה). נגדיר כ-<math>n</math> את מספר התוכניות שהסתיימו. קומבינטורית,
<math>
n
\leq
\frac
|\Sigma|^h - 1
}
{
|\Sigma| - 1
}
</math>
ולכן נניח <math>
n
=
\frac
{
|\Sigma|^h - 1
}
{
|\Sigma| - 1
}
</math>
{{להשלים}}
}}
▲{{
==תער אוקאם==
|