תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←אי-חישוביות פונקציית הסיבוכיות: עיצוב |
←הגדרות: הרחבה |
||
שורה 13:
==הגדרות==
לסיבוכיות קולמוגורוב מספר הגדרות, אשר אינן נבדלות ביניהן באופן מהותי, אלא במידת הדיוק והגמישות. נראה כעת שלוש הגדרות לסיבוכיות זו. בחלק זה נשתמש בהגדרה השלישית מביניהן.
{{הגדרה|תוכן=▼
סיבוכיות קולומוגורוב <math>K(x)</math> של מחרוזת <math>x</math>, היא אורך הקידוד המינימלי של מכונה, שעל קלט ריק עוצרת עם הפלט <math>x</math>:{{רווח קשיח|2}}▼
{{הגדרה|שם=סיבוכיות קולמוגורוב (גרסת מ"ט)|תוכן=
<center><math>K(x) = \min_{M \;:\; M(\epsilon) = x} \left|\langle M \rangle\right| </math></center>▼
סיבוכיות קולומוגורוב <math>K^{TM}(x)</math> של מחרוזת <math>x</math>, היא אורך הזוג הקצר ביותר של מ"ט וקלט, כך שתוצר פעולת המכונה על הקלט היא <math>x</math>:
<center><math>K^{TM}(x) = \min_{M, w \;:\; M(w) = x} \left|\langle M \rangle\right| +\left|w\right| </math></center>
}}
עם זאת, בפרק זה נשתמש בהגדרה גמישה יותר (ומדוייקת פחות), התופסת יותר את רוח הדברים.
ראשית, נניח שיש לנו שפת תכנות אוניברסאלית <math>U</math> כלשהי, דהיינו שפה שבעזרתה אפשר לכתוב כל שפת תכנות אחרת. (לפי [[תורת החישוביות/שקילות מודלי חישוב#התזה של צ'רץ'-טיורינג|תזת צ'רץ'-טיורינג]], כל שפה כזו שקולה בעוצמתה למ"ט.) כדוגמה לשפה כזו, אפשר לחשוב על [[פייתון]], [[שפת C]], או כל שפת תכנות כללית אחרת. בהנתן תוכנית <math>M</math> נכתוב
<math>M_U(w)</math>
כדי לתאר את תוצאת ריצתה של התוכנית <math>M</math> על קלט <math>w</math>, כאשר מפרשים אותה כתוכנית בשפה <math>U</math>.
{{הגדרה|שם=סיבוכיות קולמוגורוב (גרסת שפה אוניברסאלית מפורשת)|תוכן=
▲סיבוכיות קולומוגורוב <math>
▲<center><math>
}}
נשים לב שאם יש לנו שתי שפות אוניברסאליות, נניח <math>U</math> ו<math>U'</math>, אז סיבוכיות הקולמוגורוב של מחרוזות לא יכול להיות שונה מדי תחת שתי השפות. ככלות הכל, נניח שיש מחרוזת בעלת תוכנית קצרה מאד בפייתון המייצרת אותה, ואילו כל תוכנית בשפת C המתארת אותה ארוכה מאד. היות ששפת C היא שפה אוניברסאלית, נוכל לתאר את המחרוזת בשפת C בעזרת שילוב תיאור של שפת פייתון עצמה (בשפת C), ותיאור התכנית בשפת פייתון המייצרת את המחרוזת.
הדבר מוביל אותנו לאבחנה הבאה:
לכל שתי שפות אוניברסאליות <math>U</math> ו<math>U'</math>, קיים קבוע
<math>c = c(U, U')</math>
המקיים
<center><math>\forall_x \left| K_U(x) - K_{U'}(x) \right| \leq c.</math></center>
}}
בעקבות משפט זה, ברור שאפשר להחליט שרירותית על שפה אוניברסאלית <math>U</math> כלשהי, ולהגדיר את סיבוכיות קולמוגורוב בעזרתה. כל הגדרה בעזרת שפה אחרת, תיבדל ממנה לכל היותר בקבוע חיבורי כלשהו. נגדיר לכן את ההגדרה האחרונה, בה נשתמש בחלק זה:
{{הגדרה|שם=סיבוכיות קולמוגורוב|תוכן=
סיבוכיות קולומוגורוב <math>K(x)</math> של מחרוזת <math>x</math>, היא סיבוכיות הקולמוגורוב שלה תחת שפה אוניברסאלית <math>U</math> כלשהי:
<center><math>K(x) = K_U(x) = \min_{M \;:\; M_U(\epsilon) = x} \left|\langle M \rangle\right| </math></center>
}}
לעתים המחרוזת <math>x</math> כבר ידועה, ואנו רוצים לתאר מחרוזת נוספת, <math>y</math>. בהנחה ש<math>x</math> ו<math>y</math> מתארים דברים דומים, ייתכן שניתן להשתמש בתיאור של <math>x</math> שנתון לנו, על־מנת לתאר את <math>y</math> בצורה יותר פשוטה. לדוגמה, נניח ש<math>x</math> ו<math>y</math> מתארות כיצד לייצר את דגליהן של אירלנד ובלגיה (תמונות בצד). לאחר שנסביר מהו מלבן, מהו בד, ושאר הדברים שצריך כדי לתאר איך לייצר את דגל אירלנד, אפשר אולי לתאר את ייצור דגל בלגיה באמירה שהוא דומה לדגל אירלנד אלא שצבעיו הם כך וכך.
| |||