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

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