פונקציה חשיבה

בתורת הסיבוכיות, שהיא ענף של מדעי המחשב, פונקציה חשיבה בזמן היא פונקציה f מהמספרים הטבעיים לעצמם, וקיימת מכונת טיורינג שבהינתן קלט n, תשאיר על הסרט שלה בסוף הריצה את הפלט (f(n בזמן ריצה שלא ארוך מ-(f(n. המטרה של הגדרה זו היא לא להתייחס לפונקציות שאין להן חסם עליון על זמן הריצה של מכונות טיורינג.

פונקציה חשיבה בזמן

יש שתי הגדרות שונות לפונקציה חשיבה בזמן:

• פונקציה f תיקרא חשיבה בזמן אם קיים מספר טבעי n₀ ומכונת טיורינג M כך שלכל $n\geq n_{0}$ בהינתן הקלט 1ⁿ (המכיל n פעמים את הספרה 1) תעצור אחרי בדיוק (f(n צעדים.
• פונקציה f תיקרא חשיבה בזמן אם קיימת מכונת טיורינג M כך שבהינתן המחרוזת 1ⁿ תדפיס את הייצוג הבינארי של (f(n בזמן ((O(f(n (ניתן גם להשתמש בייצוג אונרי במקום זאת, היות שניתן לעבור בין השניים בזמן ((O(f(n).

כמו כן, פונקציה f תיקרא חשיבה באופן מלא בזמן אם קיימת מכונת טיורינג M שבהינתן הקלט 1ⁿ, תעצור אחרי (f(n צעדים.

פונקציה חשיבה במקום

באופן דומה, פונקציה f תיקרא חשיבה במקום אם קיים מספר טבעי n₀ ומכונת טיורינג M כך שלכל $n\geq n_{0}$ בהינתן הקלט 1ⁿ, תדפיס את הפלט (f(n בייצוג בינארי (או אונרי), תוך שימוש בלכל היותר ((O(f(n מקום בסרט.

פונקציה f תיקרא חשיבה באופן מלא במקום אם קיימת מכונת טיורינג M שבהינתן הקלט 1ⁿ תעצור אחרי שימוש בבדיוק (f(n תאי סרט.

דוגמאות

רוב הפונקציות השימושיות (f(n (כמו $n,n^{k},2^{n}$) הן חשיבות בזמן ובמקום, כל עוד (f(n היא לפחות cn עבור קבוע c>0. לא קיימת פונקציה שהיא (o(n וחשיבה בזמן, אלא אם כן היא קבועה החל ממקום מסוים, היות שאין מספיק זמן לקרוא את כל הקלט. לעומת זאת, הפונקציה $log(n)$ היא חשיבה במקום.

שימושים

נעשה שימוש רב בפונקציות חשיבות בזמן כנגזרת של משפט ההיררכיה בזמן. הן חשובות היות שההיררכיה מסתמכת על מכונת טיורינג שמכריעה שפה בזמן ((O(f(n בעוד שהאלגוריתם לוקח יותר מ(f(n צעדים. זה כמובן לא אפשרי בלי היכולת לחשב את (f(n בזמן הזה. נעשה שימוש בפונקציות חשיבות במקום באופן דומה במשפט ההיררכיה במקום.

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.