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

בפרק זה נגדיר במדויק את הרעיון הנ״ל תוך שימוש ב[[תורת_החישוביות/מכונת טיורינג|מכונות טיורינג]]. ב[[#הגדרות|הגדרות]] נגדיר את {{וק|סיבוכיות קולמוגורוב|סיבוכיות הקולמוגורוב}} של מחרוזת כאורך הקצר ביותר של מ"טתוכנית המייצרת אותה. רעיון זה של סיבוכיות קולמוגורוב מקשר בין תחום החישוביות לתחומים אחרים, כגון {{וק|תורת האינפורמציה|תורת האינפורמציה}}, ויש לו מספר שימושים. ב[[#אי-חישוביות פונקציית הסיבוכיות|אי-חישוביות פונקציית הסיבוכיות]] נראה שאי אפשר לחשב אותה בעזרת מחשב. ב[[#אי-דחיסות מחרוזות|אי-דחיסות מחרוזות]] נראש שלמרות שאי אפשר לחשב את סיבוכיות הקולמוגורוב של אף מחרוזת, אפשר להראות שרוב המחרוזות אינן דחיסות, במובן זה שאין להן סיבוכיות קולמוגורוב קצרה. [[#כלל השרשרת לסיבוכיות|כלל השרשרת לסיבוכיות]] נדון בסיבוכיות המותנה של מחרוזת, דהיינו סיבוכיות תיאור מחרוזת בהנחה שמחרוזת אחרת כבר ידועה.

נניח על דרך השלילה שישנה מ"טתוכנית

נגדיר מ״טתוכנית <math>M</math> בצורה הבאה. <math>M</math> מקבלת מספר חיובי <math>n</math>, ומחזירה את המחרוזת הקצרה ביותר <math>s</math> שעבורה <math>K(s) \geq n</math>. נשים לב ש<math>M</math> אכן יכולה לעשות זאת. היא מורכבת מלולאה המונה את המחרוזות בסדר לקסיקורפי (דבר שאפשר לממשו בקלות במ״ט), מקריאות ל־<math>M_K(s)</math> (שלפי הנחתנו, תמיד מסתיימות), ומהשוואה ל<math>n</math>. נגדיר את

כעת נגדיר סדרת מ"טתוכנית <math>P_i</math> (כאשר <math>i = 0, 1, 2, ,\ldots</math>) באופן הבא. <math>P_n</math> קוראת ל<math>M</math> עם פרמטר <math>n</math>

מספר מ"טהתוכנית השונות באורך פחות מ<math>|x|</math>

לכן, קומבינטורית, אין מספיק מ"טתוכנית מתאימות.

נשים לב שלו היינו יודעים את <math>K(x,y)</math>, אפשר היה למנות את איבריהן של <math>A</math> ו<math>A_x</math> באופן דומה לזה שעשינו במקומות אחרים בספר. כדי למנות את איברי <math>A</math>, נמנה ב[[w:סדר לקסיקוגרפי|סדר לקסיקוגרפי]] את כל מ"טה באורך לכל היותר <math>\left| \Sigma \right|^{K(x, y)}</math>.