שפה פורמלית
שפה פורמלית היא אוסף של מילים. מילים הן רצפים של אותיות מתוך אלפבית. אלפבית הוא קבוצה קטנה של סימנים. יש גם מילה מיוחדת בלי אותיות, זו המילה הריקה. המילה הריקה מסומנת בדרך-כלל ב־ε. למרות שהאלפבית סופי, אפשר שיהיו הרבה מאד מילים בשפה. = מושגים יסודיים בשפות פורמליות = אלפבית = קבוצת סימנים. מילה = רצ...
קבוצה ניתנת למנייה רקורסיבית
קבוצה בת מנייה היא קבוצה של מספרים. קבוצה = אוסף של מספרים. אומרים שקבוצה היא "ניתנת למנייה רקורסיבית" אם יש תוכנית מחשב שמקבלת מספר ומפסיקה כשהמספר שייך לקבוצה. מפסיקה = עוצרת. אם המספר אינו שייך, התוכנית אולי לא תפסיק בכלל. אפשר גם להגיד שיש תוכנית שמקדמת ומציגה כל המספרים של הקבוצה, אולי ברשימ...