תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←הגדרות: הגדרה ישירה, ללט מ״ט מתווכת |
←הגדרות: במחשבה שנייה, כלל לא ברור לי למה תריך הגדרה עם מ"ט אוניברסלית. זה אמנם מאפשר כלליות בהגדרת הקידוד של M אבל מרגע שקבענו את הקידוד ר |
||
שורה 17:
{{הגדרה|תוכן=
לכל מחרוזת <math>x</math> ומ"ט אוניברסלית <math>U</math>, '''[[w:סיבוכיות קולמוגורוב|סיבוכיות הקולמוגורוב]]''' של <math>x</math> יחסית ל־<math>U</math> היא תיאורה הקצר ביותר של מ"ט <math>M</math> המייצרת את <math>x</math> בהנתן המחרוזת הריקה
<math>\epsilon</math>:
<center><math>K_U(x) = \min_{M \;:\; U(M, \epsilon) = x} \left|\langle M \rangle\right| </math></center>
| |||