סיבוכיות קולמוגורוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות) מ בוט החלפות: לעיתים |
מ הוספת קישור לשנות השישים של המאה העשרים |
||
שורה 2:
סיבוכיות קולמוגורוב איננה תלויה באופן מהותי בשפת ה[[תכנות]] אליה מתייחסים מכיוון שלכל שתי שפות ניתן לכתוב תוכנית בגודל סופי המהווה [[מפרש (תוכנה)|מפרש]] (interpreter) של אחת לשנייה. הדבר נכון במיוחד כשמתעניינים בסיבוכיות קולמוגורוב של סדרה של מחרוזות,
לסיבוכיות קולמוגורוב קוראים גם "סיבוכיות אלגוריתמית". היא פותחה על ידי [[אנדריי קולמוגורוב]], מתמטיקאי [[ברית המועצות|סובייטי]], באמצע [[שנות השישים של המאה העשרים]]. במקביל הוצע הרעיון על ידי ריי סולומונוף (Ray Solomonoff) וגרגורי צ'ייטין (Gregory Chaitin).
השימוש במושג מאפשר לעיתים לפשט הוכחות מורכבות למדי. לדוגמה, ניתן להוכיח באמצעותו, במספר שורות, גרסה חלשה של [[משפט המספרים הראשוניים]].
| |||