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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
מ הגהה, מעבר ממ"ט לתוכניות
שורה 1:
{{תורת החישוביות}}
 
אינטואיטיבית, ככל שלסדרה יש סיבוכיות קולמוגורוב נמוכה יותר, כך נראה כאילו שהיא פחות רנדומית. בפרק זה נבסס קשר זה, דרך רעיון ה'''הסתברות האוניברסאלית''', שהיא הסיכוי שמחרוזת תווצר ממ"טמתוכנית שבעצמה נוצרה מתהליך אקראי. לרעיון זה יש השלכות למושגים ידועים מ[[w:פילוסופיה של המדע|פילוסופיה של המדע]], לדוגמה
[[w:תער אוקאם|תער אוקאם]].
 
שורה 8:
==הגדרות==
 
ה'''הסתברות האוניברסאלית''' של מחרוזת <math>x</math> היא הסיכוי שהיא תווצר ע"י מ"טתוכנית שבעצמה מיוצרת ע"י תהליך אקראי. נניח שאנו מייצרים מחרוזות ע"י תהליך בו כל תו מוגרל ב[[w:התפלגות אחידה|התפלגות אחידה]] עפנ"י <math>\Sigma</math>. חלק מהמחרוזות הנוצרות יהיו תיאורים חוקיים של מ"טתוכנית. חלק ממ"טמתוכנית אלה אכן ייצרו את <math>x</math> בהנתן המחרוזת הריקה. ההסתברות האוניברסאלית של המחרוזת נקבעת עפ"י זאת.
 
{{הגדרה|שם=הסתברות אוניברסאלית של מחרוזת|תוכן=
שורה 19:
נגדיר גם את '''הסתברות הקולמוגורוב''' של מחרוזת ע"י ביטוי אלגברי דומה (שלו קשה יותר למצוא מוטיווציה):
{{הגדרה|שם=הסתברות אוניברסאלית של מחרוזת|תוכן=
עבור מחרוזת <math>x</math>, נניח ש-<math>M_K(x)</math> היא מ"טתוכנית בעלת התיאור הקצר ביותר המייצרת את <math>x</math>. אז '''הסתברות הקולמוגורוב''' של <math>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>, ולכן הוא בערך