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