|
#0101010101010101010101010101010101010101
#0011010010001000010111011110101010100101
אינטואיטיבית, המחרוזת הראשונה בעלת חוקיות ברורה, ואילו השניה נראית "אקראית", חסרתוחסרת חוקיות., איךאולם מודדיםכיצד אפשר להגדיר זאת בצורה מדוייקת? נשים לב שאפשר לתאר כיצד לייצר את כמותהמחרוזת הראשונה בצורה קצרה: ה"חוקיותכתוב את הרצף '01' 20 פעמים", שלאך מחרותאת נתונה?ייצור המחרוזת השנייה כנראה שנצטרך לתאר פחות-או-יותר בעזרת תוכנה: "כתוב את הרצף 0011010010001000010111011110101010100101".
דרך אחת, היא ע״י תיאור האלגוריתם המייצר את המחרוזת. או במילים אחרות - עד כמה מורכבת מ״ט המייצרת את המחרוזת.
נשים לב שאפשר לתאר את המחרוזת הראשונה ע״י אלגוריתם קצר: "חזור 20 פעמים על הרצף 01", וכן מ״ט טיורינג המייצרת מחרוזת זו תהיה "פשוטה". את המחרוזת השניה, כנראה שיש צורך לתאר פשוט בעזרת התוכן שלה – מ״ט המתאימה תכיל מספר מצבים כאורך המחרוזת שכל מצב ידפיס תו אחד ויעבור למצב הבא.
בפרק זה נגדיר במדויק את הרעיון הנ״ל, תוך שימוש ב[[תורת_החישוביות/מכונת_טיורינג_אוניברסליתמכונת טיורינג|מ״טמכונות אוניברסליותטיורינג]]. ב[[#הגדרות|הגדרות]] נגדיר את [[w:סיבוכיות קולמוגורוב|סיבוכיות הקולמוגורוב]] של מחרוזת כאורך הקצר ביותר של מ"ט המייצרת אותה. רעיון זה של סיבוכיות קולמוגורוב מקשר בין תחום החישוביות לתחומים אחרים, כגון [[w:תורת האינפורמציה|תורת האינפורמציה]], ויש לו מספר שימושים. בפרקב[[#אי-חישוביות זהפונקציית נגדירהסיבוכיות|אי-חישוביות אתפונקציית הסיבוכיות]] נראה שאי אפשר לחשב אותה בעזרת מחשב. ב[[w:סיבוכיות#אי-דחיסות קולמוגורובמחרוזות|סיבוכיותאי-דחיסות הקולמוגורובמחרוזות]] שלנראש מחרוזתשלמרות כאורךשאי הקצראפשר ביותרלחשב שלאת מ"טסיבוכיות המייצרתהקולמוגורוב אותה,של נראהאף שאימחרוזת, אפשר לחשבלהראות אותהשרוב המחרוזות אינן דחיסות, ונדוןבמובן זה שאין להן סיבוכיות קולמוגורוב קצרה. [[#כלל השרשרת לסיבוכיות|כלל השרשרת לסיבוכיות]] נדון בסיבוכיות המותנה של מחרוזת, דהיינו סיבוכיות תיאור מחרוזת בהנחה שאחרתשמחרוזת אחרת כבר תוארהידועה.
בפרק [[תורת החישוביות/סיבוכיות קולמוגורוב/אי-דחיסות ויישומיה|אי-דחיסות ויישומיה]] נראה יישום של סיבוכיות קולמוגורוב. למרות שאי אפשר לחשב את סיבוכיות הקולמוגורוב של אף מחרוזת, אפשר להראות שרוב המחרוזות אינן דחיסות, במובן זה שאין להן סיבוכיות קולמוגורוב קצרה. יש לכך יישומים קומבינטוריים שונים.
בפרק [[תורת החישוביות/סיבוכיות קולמוגורוב/אי-דחיסות ויישומיה|אי-דחיסות ויישומיה]] נראה יישום של סיבוכיות קולמוגורוב. כאמור, אפשר להראות שלרוב המחרוזות אין סיבוכיות קולמוגורוב קצרה, ונראה יישומים קומבינטוריים שונים של רעיון זה. בפרק [[תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית|הסתברות אוניברסאלית]] נראהנבסס הלאה את סיבוכיות קולמוגורוב כמדד לסיבוכיות מחרוזות, ונראה כיצד אפשר להשתמש בסיבוכיות קולמוגורובבו כדי להגדיר הסתברות "אובייקטיווית" להווצרות מחרוזות.
==הגדרות==
| 