מילון מונחים מ-פ
מ
מכונת טיורינג היא מודל חישובי הבנויה בצורה הבאה:
המכונה מכילה בקר מרכזי שמכיל מספר סופי של מצבים (מצבי המכונה).
בנוסף, ישנו סרט מחולק למשבצות. הסרט הזה הוא אינסופי בכיוון ימין, כלומר,
יש לו קצה שמאלי.
החלק השלישי של המכונה הוא הראש קורא- כותב, שיכול לזוז ימינה ושמאלה, לקרא ולכתוב.
מכונת טיורינג לא דטרמינסטית הינה חמישיה: S,h), (Q,S Δ, = N
כאשר: Q קבוצת מצבים סופית.
S א"ב סופי ( S Î (#
Î Q h מצב עצירה.
Î Q s מצב התחלתי.
תהי S קבוצת סימנים. מערכת ריצוף מעל S הינה זוג (A=(C,c0
כאשר CεS×S×S×S קבוצת אריחים סופית.
coεC – אריח התחלתי (לפינה השמאלית התחתונה).
ס
תהי L שפה, ותהי f:N→N . נאמר כי L בעלת סיבוכיות זמן f, אם קיימת מ"ט M שפועלת בסיבוכיות זמן f ו-M מכריעה את L.
פ
פונקציה תקרא פונקציה פרימיטיבית רקורסיבית אם ניתן ליצור אותה מהפונקציות הבסיסיות על ידי שימוש בהרכבה ורקורסיה בלבד.
פונקציה תקרא פונקציה רקורסיבית אם אפשר ליצור אותה מהפונקציות הבסיסיות בשימוש של הרכבה רקורסיה ומינימיזציה.
גולשים מקוונים: 5