תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←הגדרות: הרחבה |
|||
שורה 71:
{{הוכחה|1=
(ההוכחה מעט דומה באופייה ל[[תורת החישוביות/כריעות שפות/שפות שאינן כריעות#אי-כריעות בעיית העצירה|הוכחת אי-כריעות בעיית העצירה]].)
נניח על דרך השלילה שישנה מ"ט
<math>K'</math>
המחשבת את <math>K</math>.
נגדיר את מ"ט <math>M</math> בצורה הבאה. <math>M</math> מקבלת מספר חיובי <math>n</math>, ומחזירה את המחרוזת הקצרה ביותר <math>s</math> שעבורה <math>K(s) \geq n</math>. נשים לב ש<math>M</math> אכן יכולה לעשות זאת. היא מורכבת מלולאה המונה את המחרוזות ב[[w:סדר_אלפביתי|סדר לקסיקורפי]] (דבר שאפשר לממשו בקלות במ"ט), ומקריאות ל<math>K'(s)</math> (שלפי הנחתנו, תמיד מסתיימות), ומהשוואה
<math>u</math>
כאורך
שורה 83 ⟵ 86:
כעת נגדיר סדרת מ"ט <math>P_i</math> (כאשר <math>i = 0, 1, 2, ,\ldots</math>) באופן הבא. <math>P_n</math> קוראת
כלשהו, ומחזירה את המחרוזת המוחזרת על ידה. נשים לב שתיאור <math>P</math> דורש
<math>u + \log_{\left| \Sigma \right|}\left(n\right) + c</math>
סימנים, כאשר <math>c</math> הוא קבוע כלשהו:
שורה 92 ⟵ 94:
# <math>c</math> (קבוע כלשהו) סימנים לתיאור הקריאה ל<math>M</math>.
אבל תיאור <math>P_n</math> הוא גם תיאור המחרוזת המוחזרת ממנה, נקרא לה <math>s_n</math>. לפי הגדרת <math>M</math>, ל<math>s_n</math> נדרשים לפחות
<math>n</math>
סמלים. קיבלנו, לכן, שבהכרח מתקיים
<math>u + \log_{\left| \Sigma \right|}(n) + c \geq n</math>.
שורה 101 ⟵ 103:
הדבר מפסיק להיות נכון.
}}
==אי-דחיסות מחרוזות==
| |||