בשביל להמחיש את הרעיון, ניתן לחשוב על המחרוזת הבאה: 001001001001001001001001001001001001001
מבחינת הסיבוכיות האלגוריתמית, זוהי מחרוזת פשוטה (בעלת סיבוכיות קטנה) מכיוון שהתוכנית המייצרת אותה היא פשוט לולאה הפועלת שלוש עשרה פעמים ומדפיסה: 001.
לעומת זאת, המחרוזת הבאה היא כנראה יותר מסובכת: 01100011100111100111000111000111110101101101
מכיוון שלא ניכר כלל פשוט המייצר אותה.
אי-כריעות.
לא קיים אלגוריתם המסוגל לחשב את סיבוכיות קולמוגורוב לכל מחרוזת שהיא. יתר על כן, ניתן להשתמש בסיבוכיות קולמוגורוב כדי לבנות טענות שלא ניתנות להוכחה או הפרכה במסגרת תורה מסוימת. דוגמה לתוצאה שכזו היא משפט האי-שלמות של צ'ייטין.
סיבוכיות קולמוגורוב והמושג 'מסובך'.
אחד הרעיונות מאחורי ההגדרה של סיבוכיות קולמוגורוב היא לתת הגדרה פורמלית למושג האינטואיטיבי 'מסובך', וניתן לשאול האם ההגדרה הזאת אכן מצליחה לבטא את מה שנתפס אצלנו בתור מסובך. למשל, ידוע שתוכנות פשוטות ביותר, הדורשות מספר קטן מאוד של שורות קוד, יכולות ליצור התנהגות מורכבת מאוד ומסובכת. באופן דומה בתחומים רבים בפיזיקה ובמתמטיקה, בעיקר במערכות פרקטליות וכאוטיות התנהגות מסובכת מאוד נוצרת מתוך חוקי בסיס פשוטים. בקריפטוגרפיה ידועים מחוללים פסאודו אקראיים המותחים גרעין (seed) קצר
למחרוזת ארוכה, שלא ניתן להבדיל, באופן אפקטיבי, בינה לבין מחרוזת אקראית (על סמך הנחות מקובלות). סיבוכיות קולמוגורוב של מחרוזות כאלה היא קטנה (תיאור הגרעין). לעומת זאת סיבוכיות קולמוגורוב של מחרוזת אקראית היא בהסתברות גבוהה כמעט כאורכה.
ביסוס מתמטי.
נניח שאנו רוצים לתאר אובייקט נתון על ידי מחרוזת בינארית סופית. אין זה מן העניין אם לאובייקט יש תיאורים רבים; עם זאת, כל תיאור צריך לתאר רק אובייקט אחד. מבין כל התיאורים של אובייקט ניתן לקחת את אורך התיאור הקצר ביותר כמדד לסיבוכיות האובייקט. טבעי לקרוא לאובייקט 'פשוט' אם יש לו לפחות תיאור קצר אחד, ולקרוא לו 'מסובך' אם כל התיאורים שלו ארוכים.
אבל כעת הגדרה זו נופלת למלכודת המתוארת בפרדוקס של ברי, שבו מגדירים מספר טבעי כ"מספר הכי פחות טבעי שלא ניתן לתאר בפחות מ-20 מילים". אם המספר הזה אכן קיים, זה עתה קיבל תיאור בן 10 מילים, בניגוד להצהרה ההגדרתית שלו. אם מספר כזה אינו קיים, ניתן לתאר את כל המספרים הטבעיים בפחות מ-20 מילים. לכן אמורים לבחון בזהירות רבה את המושג 'תיאור'.
נניח שכל תיאור מתאר אובייקט אחד לכל היותר. כלומר, יש שיטת מפרט formula_1 שמשייכת לכל היותר אובייקט אחד formula_2 לתיאור formula_3. זה אומר ש-formula_1 היא פונקציה מקבוצת התיאורים, נניח formula_5, לתוך קבוצת האובייקטים, נניח formula_6. נראה גם הגיוני לדרוש שלכל אובייקט formula_2 ב-formula_6 יהיה תיאור formula_3 ב-formula_5 כך שניתן לכתוב formula_11. כדי להפוך תיאורים לשימושיים הם אמורים להיות סופיים. זה אומר שיש רק תיאורים רבים לספור. מכיוון שיש תיאור לכל אובייקט, יש גם רק אובייקטים רבים שניתן לתאר. כיצד מודדים את מורכבות התיאורים?
בהסתמך על תורת החישוביות, מבטאים תיאורים כרצפים סופיים של 0 ו-1. בטכנולוגיית תקשורת, אם שיטת המפרט formula_1 ידועה גם לשולח וגם למקבל, אזי ניתן להעביר הודעה formula_2 משולח למקבל על ידי שידור הרצף של 0 ו-1 של תיאור formula_3 עם formula_11. העלות של שידור זה נמדדת לפי מספר ההתרחשויות של 0 ו-1 ב-formula_3, כלומר באורך של formula_3. העלות הנמוכה ביותר של שידור של formula_2 נתונה באורך של formula_3 הקצר ביותר כך ש-formula_11. בתקשורת בוחרים את העלות הנמוכה ביותר של שידור כמורכבות התיאורית של formula_2 לפי שיטת המפרט formula_1.
ברור שהמורכבות התיאורית הזו של formula_2 תלויה באופן מכריע ב-formula_1. העיקרון הכללי המעורב הוא שהמסגרת התחבירית של שפת התיאור קובעת את תמציתו של התיאור. על מנת להשוות באופן אובייקטיבי מורכבויות תיאוריות של אובייקטים, כדי להיות מסוגלים לומר "formula_2 מורכב יותר מ-formula_26", המורכבות התיאורית של formula_2 צריכה להיות תלויה ב-formula_2 בלבד. ניתן לראות את המורכבות הזו כקשורה לשיטת תיאור אוניברסלית שמניחים מראש כל השולחים והמקבלים. מורכבות זו היא אופטימלית אם אין שיטת תיאור אחרת מקצה מורכבות נמוכה יותר לאובייקט כלשהו.
בתיאור הסיבוכיות לא באמת מעוניינים באופטימיות ביחס לכל שיטות התיאור. כדי שמפרטים יהיו שימושיים בכלל, יש צורך שהמיפוי מ-formula_3 ל-formula_30 יהיה ניתן לביצוע בצורה יעילה. כלומר, זה יכול לפחות באופן עקרוני להתבצע על ידי בני אדם או מכונות. תפיסה זו מעבירה את השאלה לתחום פונקציות ניתנות לחישוב חלקיות. לפי נקודות מבט מתמטיות מקובלות, זה עולה בקנה אחד עם הרעיון האינטואיטיבי של חישוב יעיל. קבוצת הפונקציות הניתנות לחישוב חלקיות מכילה פונקציה אופטימלית אשר ממזערת את אורך התיאור של כל פונקציה אחרת כזו. פונקציה זו תסומן ב-0formula_1. עבור כל פונקציה אחרת לחישוב formula_1, עבור כל האובייקטים formula_6, יש תיאור של formula_2 מתחת ל-0formula_1 שהוא קצר יותר מכל תיאור של formula_2 מתחת ל-formula_1. (כלומר, קצר יותר עד קבוע מתוסף שאינו תלוי ב-formula_2.) לפי חשיבה זו מורכבותו של אובייקט היא תכונה אובייקטיבית של האובייקט המתואר בלבד: היא תכונה מהותית של אותו אובייקט, והיא אינה תלויה בפורמליזם התיאור. ניתן להתייחס למורכבות זו כתוכן מידע מוחלט: כמות המידע שיש להעביר בין כל השולחים והמקבלים כאשר הם מעבירים את המסר בהיעדר כל ידע אפריורי אחר המגביל את תחום ההודעה.
בגדול, זה אומר שכל תחבירי התיאור שהם חזקים מספיק כדי לבטא את הפונקציות הניתנות לחישוב חלקיות הם תמציתיים בערך באותה מידה. ניתן לבטא את כל האלגוריתמים בכל שפת תכנות כזו באופן תמציתי באותה מידה, עד למונח קבוע מתוסף קבוע. התועלת המדהימה והנכונות המובנית של התיאוריה של מורכבות קולמוגורוב נובעת מעצמאות זו של שיטת התיאור.
וסטווינד
מטוס הווסטווינד (באנגלית: IAI Westwind) מתוצרת התעשייה האווירית לישראל הוא מטוס מנהלים דו-מנועי אשר יכול לשאת בין שבעה לעשרה נוסעים. המטוס המוצלח נתן לחברה דריסת הרגל בשוק התעופה האזרחית. קו הייצור של המטוס פעל במשך כעשרים שנה.
מטוסי השחף, המבוססים על ווסטווינד, פעלו בשירות חיל האוויר הישראלי בגף סיורי ים של הטייסת הבינלאומית.
היסטוריה.
פיתוח המטוס.
תכנונו של הווסטווינד מתבסס על תכנון של חברת Aero Commander למטוס סילוני בשם Jet Commander שהתבסס בעצמו על מטוס קודם של אותה חברה שהיה בעל שני מנועי מדחף (ונקרא, כמו החברה, Aero Commander). ה-Jet Commander טס לראשונה ב-2 בינואר 1963 (תחת השם "Aero Commander 1121 Jet Commander") ולאחר תקופת מבחן נכנס לייצור סדרתי ונמסר ללקוחות החל בשנת 1965. זמן קצר לאחר מכן נרכשה חברת Aero Commander על ידי חברת רוקוול אינטרנשיונל, שלה היה כבר מטוס מנהלים דומה - ה-Rockwell Sabreliner ונאסר עליה לייצר את שני המטוסים במקביל בשל חוקים נגד מונופול. ברוקוול הוחלט למכור את הזכויות על הג'ט קומנדר והתעשייה האווירית רכשה אותן בשנת 1967. בינואר 1970 נערכה טיסת הבכורה של הג'ט קומנדר הראשון שייצרה התעשייה האווירית.
ייצור בתעשייה האווירית.
בתעשייה האווירית יוצרו 150 מטוסים על פי התכנון המקורי כדי למלא את ההזמנות שעליהן התחייבה חברת Aero Commander, ואז פנו מהנדסי החברה לשיפור התכנון. הם האריכו את גוף המטוס והוסיפו לו מכלי דלק בקצות הכנף. זמן קצר לאחר תחילת הייצור של הדגם הוחלפו מנועי הטורבו סילון במנועי טורבו מניפה חסכוניים יותר. הדגם החדש קיבל את השם "ווסטווינד" (או דגם 1123). הוא קיבל רישוי טיסה בארצות הברית בדצמבר 1971. תחום ייצור המטוסים בתעשייה האווירית הגיעה לאיזון תקציבי ב-1975.
ב-1974 הוחל בפיתוח דגם חדש של ה"ווסטווינד" (דגם 1124). הוא הוצג לראשונה במאי 1975, טיסת הבכורה נערכה ב-22 ביוילי 1975. והוא קיבל רישוי טיסה בארצות הברית במרץ 1976. עד 1978 כבר נמכרו 95 מטוסים מדגם זה, ובסך הכל החזיקה התעשייה האווירית נתח של כ-10% משוק מטוסי המנהלים בארצות הברית באותן שנים.
ווסטווינד 2.
באוקטובר 1979 הוצג הדגם החדש של המטוס שעבר שיפורים, תוכננה עבורו כנף חדשה והוספו לו כנפונים בקצות הכנף. פנים המטוס עבר שינויים רבים נוספים, והמטוס קיבל את השם "ווסטווינד 2" - "Westwind II". בשנת 1980 נמכרו 73 יחידות בשווי כולל של 200 מיליון דולר. בשנת 1982 החזיקה התעשייה האווירית כבר נתח של כ-25% משוק מטוסי המנהלים בארצות הברית.
המטוס האחרון ירד מפס הייצור בשנת 1987, לאחר ש-244 מטוסים נבנו.
בשנת 2000 השיקה התעשייה האווירית תוכנית השבחה ללקוחות המטוס. אפשרויות השבחה כללו: שדרוג המנועים, שיפור מערכות האוויוניקה, השבחה לעיצוב הפנים וכלל מערכות המטוס.
סי-סקאן/שחף.
שחף הוא הכינוי בצה"ל למטוס סיור ימי סילוני מדגם "סי-סקאן" המבוסס על הווסטווינד מתוצרת התעשייה האווירית. תכנון המטוס החל בשנת 1976, בעקבות הפיגוע במלון סבוי בתל אביב במרץ 1975, שבו שמונה מחבלים חדרו בסירת גומי לחוף הים של ת"א.