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