תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←בניית עץ השיוך: הרחבה |
מ הגהה, מעבר ממ"ט לתוכניות |
||
שורה 1:
{{תורת החישוביות}}
אינטואיטיבית, ככל שלסדרה יש סיבוכיות קולמוגורוב נמוכה יותר, כך נראה כאילו שהיא פחות רנדומית. בפרק זה נבסס קשר זה, דרך רעיון ה'''הסתברות האוניברסאלית''', שהיא הסיכוי שמחרוזת תווצר
[[w:תער אוקאם|תער אוקאם]].
שורה 8:
==הגדרות==
ה'''הסתברות האוניברסאלית''' של מחרוזת <math>x</math> היא הסיכוי שהיא תווצר ע"י
{{הגדרה|שם=הסתברות אוניברסאלית של מחרוזת|תוכן=
שורה 19:
נגדיר גם את '''הסתברות הקולמוגורוב''' של מחרוזת ע"י ביטוי אלגברי דומה (שלו קשה יותר למצוא מוטיווציה):
{{הגדרה|שם=הסתברות אוניברסאלית של מחרוזת|תוכן=
עבור מחרוזת <math>x</math>, נניח ש-<math>M_K(x)</math> היא
<center><math>
P_K(x) = \left| \Sigma \right|^{- \left| \langle M_K(x) \rangle \right|} = \left| \Sigma \right|^{- K(x)}.
שורה 138:
ראשית, נשים לב שעבור קבוע <math>c_1 > 0</math> כלשהו,
<center><math>\sum_y P_K(1^ny) \simeq P_K(1^{\infty}) = c_1,</math></center>
מפני שסביר
<center><math>\sum_y P_K(1^n1y) \simeq c_1.</math></center>
באופן דומה, סביר להניח שהתוכנית הקצרה ביותר המדפיסה <math>n</math> אחדות ולאחריהן אפס, אומרת "הדפס <math>n</math> אחדות ולאחריהן אינסוף אפסים". אורך תוכנית זו נקבע כנראה בעיקר ע"י תיאור <math>n</math>, ולכן הוא בערך
|