פונקציית אקרמן
פונקציית אקרמן היא כלל שמייצר מספרים. היא מיוחדת כי היא קוראת לעצמה שוב ושוב. זה נקרא רקורסיה. הפונקציה הזו גדלה מאוד מהר. החוק עובד בשלושה מקרים פשוטים: אם m שווה 0 מוסיפים 1 ל-n. אם m גדול מ-0 ו-n שווה 0 מחזירים ערך עם m-1 ו-1. אם שניהם גדולים, קוראים קודם ל-A(m,n-1) ואז ל-A(m-1,...) שוב. A(2,2)...
בעיית התפוצצות מצבים
התפוצצות קומבינטורית היא כשמשהו גדל מאוד מהר. קומבינטורית קשורה לספירה ולסידור של דברים. דוגמאות קצרות: פונקציית העצרת. העצרת מחשבת את המכפלה של כל המספרים מ‑1 ועד מספר נתון. יש גם פונקציית אקרמן. בתוכנה יש 'התפוצצות מצבים'. זה כשיש המון דרכים שהתוכנה יכולה לפעול בהן. גם תוספת קטנה של קלט יכולה לי...