הועלה לאתר:  
מספר עמודים: 32
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת החישוביות - חלק ראשון

סיכום מאת: ניר אדר

7.2. סיבוכיות קולמגורוב

הגדרה: למען הפשטות נגדיר plot:$\Sigma  = \left\{ {0,1} \right\}$ וכן plot:$\Gamma  = \left\{ {0,1,\flat } \right\}$. בהינתן מחרוזת plot:$x \in {\Sigma ^*}$, נגדיר את סיבוכיות קולמגורוב של plot:$x$, plot:$k\left( x \right)$, בתור מספר המצבים הקטן ביותר של מ"ט שמוציאה פלט plot:$x$ על plot:$\varepsilon $ (המילה הריקה). פונקציה זו הינה plot:$k:{\left\{ {0,1} \right\}^*} \to \mathbb{N}$.

אבחנה 1: plot:$k\left( x \right) \leqslant \left| x \right| + 1$, וכן plot:$k\left( x \right)$ היא פונקציה מלאה. בהינתן plot:$x = {x_1},{x_2}...,{x_n}$ קיימת plot:${M_x}$ עם המצבים plot:${q_1},{q_2},...,{q_{n + 1}}$ כשהמצב plot:${q_i}$ מדפיס את plot:${x_i}$ ועובר למצב הבא.

אבחנה 2: לכל plot:$n \in \mathbb{N}$ קיים plot:$x$ כך שמתקיים plot:$k\left( x \right) > n$ - כלומר plot:$k\left( x \right)$ הינה פונקציה לא חסומה.

הוכחה: יהי plot:$n \in \mathbb{N}$ כלשהו. מספר המכונות בעלות לכל היותר plot:$n$ מצבים הוא plot:$\delta :Q \times \Gamma  \to Q \times \Gamma  \times \left\{ {L,R,S} \right\}$ כלומר: plot:${\left( {9k} \right)^{3k}}$ מכונות שונות לכל היותר. כל מכונה plot:$M$ מועמדת להיות מ"ט מינימלית רק עבור plot:$x$ בודד שהוא הפלט שלה על plot:$\varepsilon $. מספר המחרוזות עבורן plot:$k\left( x \right) \leqslant n$ סופי. כיוון שקיימות plot:$\infty $ מחרוזות, הטענה נובעת.

משפט: הפונקציה plot:$k\left( x \right)$ איננה ניתנת לחישוב.

הוכחה: נניח בדרך השלילה כי plot:$k\left( x \right)$ ניתנת לחישוב plot:$ \Leftarrow $ קיימת plot:${M_k}$ המקבלת מחרוזת plot:$x$ ופולטת את plot:$k\left( x \right)$. נבנה מכונה plot:${M_1}$ כך ש: plot:${M_1}$ מפרשת את הקלט כמספר טבעי plot:$n$ ופולטת plot:$y$ כך ש-plot:$y$ הוא המחרוזת הראשונה בסדר לקסיקוגרפי המקיימת plot:$k\left( y \right) > n$.

אבחנה: plot:${M_1}$ תמיד עוצרת.

יהי plot:$t$ מספר המצבים של plot:${M_1}$. ניקח מספר טבעי plot:$N$ כך שמתקיים: plot:${2^N} + N + 10 \geqslant t$.

נבנה את המכונה plot:${M_2}$ על קלט plot:$\varepsilon $:

  1. plot:${M_2}$ כותבת על הסרט את plot:${2^N}$ בייצוג בינארי.
  2. לאחר מכן המכונה חוזרת אל התחלת הסרט, ומריצה על הסרט את plot:${M_1}$.
  3. כאשר plot:${M_1}$ פולטת תוצאה, plot:${M_2}$ פולטת כמוה ועוצרת.


נתבונן בפלט של plot:${M_2}$ על plot:$\varepsilon $. נסמן את פלט זה ב-plot:$z$. כעת:

א.      מצד אחד, מתקיים כי plot:$k\left( z \right) > {2^N}$, עקב האופן בו בנינו את plot:${M_1}$.

ב.      מצד שני:

  • plot:${M_2}$ בתגובה ל-plot:$\varepsilon $ פולטת את plot:$z$.
  • מספר המצבים של plot:${M_2}$ הוא plot:$t + N + 10$:

    - plot:$t$ הוא מספר המצבים של plot:${M_1}$.

    - N אלו מצבים נוספים על מנת שהמכונה תהיה מסוגלת להדפיס את plot:${2^N}$.

    - 10 מצבים נוספים הינם מצבי עזר לצורך ההדפסה שהמכונה משתמשת בהן (יכולנו

      לבחור גם מספר אחר.

משני כיוונים אלו אנחנו מקבלים כי: plot:$k\left( z \right) \leqslant t + N + 10 < {2^N}$ וקיבלנו סתירה.

מכאן אנחנו מסיקים: הפונקציה plot:$k\left( x \right)$ איננה ניתנת לחישוב.



תגיות המסמך:

לפרק הקודם7.1. הגדרות בסיסיות
לפרק הבא8. בעיות חיפוש
מאת: דנה

החלק הראשון

בבקשה
מאת: אני

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299
מאת: רועי

אני חייב את המסמך הזה...הצילו

מאת: חשוון

מתי המסמך יחזור?
שיתוף:
| עוד