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