ויקיספר

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Atavory (שיחה | תרומות)
7,521 עריכות
מ ←‏הגדרות: עריכה
Atavory (שיחה | תרומות)
7,521 עריכות
מ ←‏הגדרות: הגהה
שורה 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)}.
</math></center>
}}
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/סיבוכיות_קולמוגורוב/הסתברות_אוניברסאלית"