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

ה'''הסתברות האוניברסאלית''' של מחרוזת <math>x</math> היא הסיכוי שהיא תווצר ע"י מ"ט שבעצמה מיוצרת ע"י תהליך אקראי. נניח שאנו מייצרים מחרוזות ע"י תהליך בו כל תו מוגרל ב[[w:התפלגות אחידה|התפלגות אחידה]] עפנ"י <math>\Sigma</math>. חלק מהמחרוזות הנוצרות יהיו תיאורים חוקיים של מ"ט. חלק ממ"ט אלה אכן ייצרו את <math>x</math> בהנתן המחרוזת הריקה. ההסתברות האוניברסאלית של המחרוזת נקבעת עפ"י זאת.

 

ה'''הסתברות האוניברסאלית''' של מחרוזת <math>x</math> היא

<center><math>

 

נגדיר גם את '''הסתברות הקולמוגורוב''' של מחרוזת ע"י ביטוי אלגברי דומה (שלו קשה יותר למצוא מוטיווציה):

עבור מחרוזת <math>x</math>, נניח ש-<math>M_K(x)</math> היא מ"ט בעלת התיאור הקצר ביותר המייצרת את <math>x</math>. אז '''הסתברות הקולמוגורוב''' של <math>x</math> היא

<center><math>