בתורת הסיבוכיות ובתורת הרקורסיה,מודל חישובי הוא אוסף של פעולות המותרות בחישוב והעלות שלהן. מודלים אלו משמשים למדידת המורכבות שלאלגוריתם מבחינתזמן ריצה אוזיכרון, ואף עונים על שאלות מהצורה: "בהינתן מודל חישובי מסוים, האם ניתן להכריע בעיה מסוימת, ובכמה זמן?"

ערך מורחב –אוטומט סופי

אוטומט סופי דטרמיניסטי הוא חמישייה${\displaystyle A=(Q,\mathrm{\Sigma },q_0,\delta ,F)}$ כאשר:

• ${\displaystyle Q}$ היא קבוצת המצבים האפשריים באוטומט.
• ${\displaystyle \mathrm{\Sigma }}$ היא הא"ב הסופי של השפה שהאוטומט מתאר.
• ${\displaystyle q_0}$ הוא המצב ההתחלתי באוטומט
• ${\displaystyle \delta :Q\times \mathrm{\Sigma }\to Q}$ היא פונקציית המעברים. כלומר,${\displaystyle \delta }$ מקבלת מצב ואות קלט, ומחזירה את המצב הבא.
• ${\displaystyle F\subseteq Q}$ היא קבוצת המצבים המקבלים באוטומט.

האוטומט מקבל מילת קלט${\displaystyle w\in {\mathrm{\Sigma }}^{\ast }}$ (נוכל גם לומר כי), וקורא את האותיות בה בזו אחר זו. הוא מתחיל את ריצתו על המילה במצב${\displaystyle q_0}$, משם עובר למצב${\displaystyle q_1=\delta (q_0,w_0)}$, וכך הלאה (באמצעות הכלל${\displaystyle q_i=\delta (q_{i-1},w_{i-1})}$. נאמר כי המילה שייכת לשפת האוטומט,אם"ם הריצה של האוטומט על המילה מסתיימת במצב מקבל, כלומר,${\displaystyle q_{|w|}\in F}$.

קיימים שני סוגים של אוטומט סופי:אוטומט סופי דטרמיניסטי ואוטומט סופי לא דטרמיניסטי. משפט הדטרמיניזציה קובע כי שני המודלים הללו שקולים מבחינת יכולת החישוב שלהם, כלומר לכל אוטומט סופי לא דטרמיניסטי${\displaystyle N}$ קיים אוטומט סופי דטרמיניסטי${\displaystyle A}$ כך שמתקיים${\displaystyle L(A)=L(N)}$.

זהו מודל חישובי פשוט למדי. משפחת השפות שניתנות לקבלה על ידי אוטומט סופי היא משפחתהשפות הרגולריות. אלו גם בדיוק השפות שניתנות ליצירה בעזרתדקדוקים רגולרים.

ערך מורחב –אוטומט מחסנית

אוטומט מחסנית הוא מודל חישובי שמהווה הרחבה לאוטומט סופי דטרמיניסטי על ידי הוספתמחסנית שבה האוטומט מסוגל לאחסן מידע. הרחבה זו מגדילה את כוחו של האוטומט, כלומר את מחלקת השפות שהוא מסוגל לזהות.

פורמלית, אוטומט מחסנית הוא השישייה${\displaystyle M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F)}$ כאשר:

• ${\displaystyle Q}$ היא קבוצת המצבים ההתחלתיים.
• ${\displaystyle \mathrm{\Sigma }}$ היא הא"ב הסופי שמעליו מוגדרת שפת האוטומט.
• ${\displaystyle \mathrm{\Gamma }}$ היא הא"ב הסופי של המחסנית (קבוצת האותיות שיכולה להיכתב במחסנית).
• ${\displaystyle \delta :Q\times (\mathrm{\Sigma }\cup \{\epsilon \})\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }}$ היא פונקציית המעברים, המקבלת מצב, אות קלט, ואות מחסנית (לקריאה) ומחזירה את המצב הבא ואות מחסנית (לכתיבה במחסנית).
• ${\displaystyle q_0\in Q}$ המצב ההתחלתי.
• ${\displaystyle F\subseteq Q}$ קבוצת המצבים המקבלים.

ניתן להגדיר את שפת האוטומט בשני אופנים:

• באמצעות מצבים מקבלים: שפת כל המילים שהאוטומט מקבל כקלט ומסיים את ריצתו עליהן במצב מקבל. נסמן שפה זו ב-${\displaystyle L_f(M)}$.
• באמצעות ריקון מחסנית: שפת כל המילים שהאוטומט מקבל כקלט ומסיים את ריצתו עליהן עם מחסנית ריקה. נסמן שפה זו ב-${\displaystyle L_e(M)}$.

ניתן להראות שאם שפה ניתנת לקבלה בשיטה אחת מהנ"ל, אז ניתן לבנות אוטומט אחר שיקבל אותה בשיטה השנייה. משפחת השפות שניתנות לקבלה על ידי אוטומט סופי היא משפחתהשפות החסרות-הקשר. אלו גם בדיוק השפות שניתנות ליצירה בעזרתדקדוקים חסרי-הקשר.

ערך מורחב –מכונת טיורינג

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

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

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

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

לעיתים עלויות היחידה של מודל מסוים נוקשות יותר מהעלות שניתן ליישם במציאות, ועל כן עלולים להיות אלגוריתמים מהירים יותר ממה שניתן היה לצפות באופן נאיבי.

• אוטומט סופי דטרמיניסטי
• אוטומט סופי לא דטרמיניסטי
• שפה רגולרית
• שפות חסרות הקשר
• פונקציה רקורסיבית
• תחשיב למדא
• מכונת טיורינג הסתברותית
• ההיררכיה של חומסקי

מדיה וקבצים בנושאמודל חישובי בוויקישיתוף

• סיבוכיות
• רקורסיה