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

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