סיבוכיות- הגדרה
הגדרה: תהי M מ"ט. נסמן ב-TM(X) את מספר הצעדים ש-M מבצעת על הקלט X.
TM(X): ∑*→N U {∞}- זוהי פונקציה שמקבלת מחרוזת ומחזירה את מספר הצעדים
שהמכונה M מבצעת עליה.
נאמר כי M פועלת בסיבוכיות זמן f אם לכל Xε∑* מתקיים: TM(X)≤f(|X|)
ז"א שיש חסם עליון למספר הצעדים שהמכונה עושה.
הגדרה: תהי L שפה, ותהי f:N→N . נאמר כי L בעלת סיבוכיות זמן f, אם קיימת מ"ט M שפועלת בסיבוכיות זמן f ו-M מכריעה את L.
משפט: תהי {P={x|x=xR שפת הפולינדרומים. אזי במ"ט עם סרט בודד ל-P סיבוכיות זמן
לפחות Ω(n2) .
משפט (ההאצה): תהי L שפה כך ש-L בעלת סיבוכיות זמן f.
אזי לכל α > 0 קבוע, L הינה בעלת סיבוכיות זמן αf(n)+4n כאשר n
הינו גודל הקלט.
מעניין אותנו α-ים קטנים, למשל ⅓=α . אז אומרים שאם L בעלת סיבוכיות f , אז גם
בעלת סעבוכיות f0.5 , f0.0001 וכן הלאה. ז"א שיש מ"ט אחרת
שיכולה להכריע את L בקבוע קטן יותר, כמובן שטבלת המעברים שלה גדולה יותר.
מסקנה: המודל של מכונת טיורינג לא רגיש מספיק בשביל להבחין בין קבועים.
באותו אופן, גם המחשב לא רגיש לקבועים, לכן אנו מדברים על סיבוכיות כזו.
גולשים מקוונים: 4