תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←בניית עץ השיוך: הגהה |
|||
שורה 105:
ולכן
<center><math>
n_1(
\left\lceil
\log_{3} \left( \frac{1}{\frac{1}{3}} \right)
שורה 120:
נניח שהתוכנית השניה שהסתיימה היא התוכנית שתיאורה הוא באורך מיליארד, והפלט שלה הוא שוב "000111000". בשלב זה,
<center><math>
P_U^2(
</math></center>
ולכן
<center><math>
n_2(
\left\lceil
\log_{3} \left( \frac{1}{\frac{1}{3} + 3^{-1,000,000,000}} \right)
שורה 138:
נמשיך כך הלאה. לדוגמה (בתרשים "בניית העץ 2" המצוייר בצד שמאל), נניח שהתוכנית השלישית שהסתיימה היא התוכנית שתיאורה הוא "" (המחרוזת הריקה), והפלט שלה הוא "011". בשלב זה,
<center><math>
P_U^3(
</math></center>
ולכן
<center><math>
n_3(
\left\lceil
\log_{3} \left( \frac{1}{1} \right)
| |||