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