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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 153:
</math></center>.
}}
(הוכחת המשפט נמצאת ב[[תורת החישוביות/סיבוכיות קולמוגורוב/תרגילים#רוב המחרוזות אינן דחיסות במיוחד|תרגיל: רוב המחרוזות אינן דחיסות במיוחד]].)
נשים לב שמשמעות הביטוי היא ש99.9% מהמחרוזות אינן דחיסות ביותר מ10 תווים!
 
שורה 168 ⟵ 169:
<math>M(x) = x </math>.
נוכל לתאר כל מחרוזת <math>x</math> בעזרת
<math>\langle M \rangle </math> שלאחריה משורשר <math>x</math>.
}}