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