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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
מ ←‏הגדרות: הגהה, עיצוב
Gran (שיחה | תרומות)
שורה 75:
 
==אי-דחיסות מחרוזות==
למרות שלא קיים אלגוריתם (מ״ט) שמחשב את סיבוכיות הקולמוגורוב של כל מחרוזת נתונה, קיימים מספר חסמים על סיבוכיות זו.
קל לראות, שהסיבוכיות של מחרוזת <math>x</math> לא תהיה גדולה בהרבה מאורך המחרוזת עצמה.
{{טענה|תוכן=
קיים קבוע <math>c</math> שעבורו, לכל מחרוזת <math>x</math>,{{רווח קשיח|2}}
<math>K(x) \leq |x| + c</math>
}}
 
{{הוכחה|1=
למרות שאי אפשר לחשב את סיבוכיות הקולמוגורוב של סדרה, קיימות מחרוזות שסיבוכיות הקולמוגורוב שלהן איננה קטנה יותר מארכן.
ברור שאפשרניתן לתאר את המחרוזת <math>x</math> ע"י התיאור "להלן המחרוזת המבוקשת" שלאחריה פשוט המחרוזת <math>x</math>.
 
פורמאלית, נניח מ"טמ״ט <math>M</math> הדפיסההמדפיסה את הקלט שלה:
<math>M(x) = x </math>. כעת נוכל לתאר כל מחרוזת <math>x</math> בעזרת
<math>\langle M \rangle </math> שלאחריה משורשר <math>x</math>.
}}
 
למרות שאי אפשר לחשב את סיבוכיות הקולמוגורוב של סדרהבנוסף, קיימות מחרוזות שסיבוכיות הקולמוגורוב שלהן איננה קטנה יותר מארכן.
{{משפט
|שם=קיום מחרוזות אי-דחיסות
שורה 122 ⟵ 136:
(הוכחת המשפט נמצאת ב[[תורת החישוביות/סיבוכיות קולמוגורוב/תרגילים#רוב המחרוזות אינן דחיסות במיוחד|תרגיל: רוב המחרוזות אינן דחיסות במיוחד]].)
נשים לב שמשמעות הביטוי היא ש99.9% מהמחרוזות אינן דחיסות ביותר מ10 תווים!
 
 
נציין שלכוון השני ישנו כמובן החסם הטריוויאלי הבא.
{{טענה|תוכן=
קיים קבוע <math>c</math> שעבורו, לכל מחרוזת <math>x</math>,
<math>K(x) \leq |x| + c</math>
}}
 
{{הוכחה|1=
ברור שאפשר לתאר את המחרוזת <math>x</math> ע"י התיאור "להלן המחרוזת המבוקשת" שלאחריה פשוט המחרוזת <math>x</math>.
 
פורמאלית, נניח מ"ט <math>M</math> הדפיסה את הקלט שלה:
<math>M(x) = x </math>.
נוכל לתאר כל מחרוזת <math>x</math> בעזרת
<math>\langle M \rangle </math> שלאחריה משורשר <math>x</math>.
}}
 
==כלל השרשרת לסיבוכיות==