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

הפונקציה <math>K(\cdot)</math> אינה נתנתניתנת לחישוב.{{רווח קשיח|2}}

<math>K'M_K</math>

המחשבת את <math>K(\cdot)</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'M_K(s)</math> (שלפי הנחתנו, תמיד מסתיימות), ומהשוואה ל<math>n</math>. נגדיר את

# <math>u</math> סימנים נדרשים לתיאור <math>K'M_K</math>