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