פונקציה פרימיטיבית רקורסיבית
פונקציה היא חוק שמקבל מספרים ומחזיר מספר. פונקציה פרימיטיבית רקורסיבית בונים משתי פעולות פשוטות וחוקים שחוזרים על עצמם. הפונקציות הפשוטות הן: אפס (מחזירה 0), העוקב (מוסיף 1), ובחירת רכיב (מחזירה אחד מהמספרים שהכנסת). חיבור של מספרים נוצר כך: אם מוסיפים 1 שוב ושוב מגיעים לתוצאה. לכן חיבור הוא פונ...
קבוצה רקורסיבית
רקורסיבית (או כריעה) אומרת שיש אלגוריתם, סדרת הוראות, שמחליט אם מספר שייך לקבוצה. תת‑קבוצה S של המספרים הטבעיים היא רקורסיבית אם יש פונקציה ניתנת לחישוב f. פונקציה היא חוק שמקבל מספר ומחזיר מספר. f מחזירה 0 כש־x שייך ל‑S, ושונה מאפס אם לא. ...
קבוצה ניתנת למנייה רקורסיבית
קבוצה בת מנייה היא קבוצה של מספרים. קבוצה = אוסף של מספרים. אומרים שקבוצה היא "ניתנת למנייה רקורסיבית" אם יש תוכנית מחשב שמקבלת מספר ומפסיקה כשהמספר שייך לקבוצה. מפסיקה = עוצרת. אם המספר אינו שייך, התוכנית אולי לא תפסיק בכלל. אפשר גם להגיד שיש תוכנית שמקדמת ומציגה כל המספרים של הקבוצה, אולי ברשימ...
פונקציה רקורסיבית
פונקציה רקורסיבית היא חוק שמקבל מספרים ומחזיר מספר. "ניתנת לחישוב" פירושו שאפשר לבצע את החוק בצעדים מסודרים, כמו אלגוריתם. פונקציות פרימיטיביות בונים מחוקים פשוטים וחזרה חוזרת. הן תמיד מפיקות תשובה ומסתיימות על כל קלט. הרבה פעולות חשבון יומיומיות הן כאלה. מוסיפים אופרטור בשם μ (מי). אופרטור זה מ...
הגדרה רקורסיבית
הגדרה רקורסיבית היא הגדרה שמפנה חזרה אל עצמה, אבל בדרך אחרת. תמיד יש גם חוק שעוצר את זה. החוק שנעצור בו קוראים תנאי עצירה. דוגמה פשוטה: להגיד "יהודי מי שאמו יהודיה". כאן בודקים את האם במקום את האדם. בדוגמה מתמטית: עצרת. כותבים 0! = 1. ואז n! = n · (n-1)! לכל שאר המספרים. כך בונים את הערך מהערך הפש...
פלאוגרפיה
פלאוגרפיה היא חקר איך נראית הכתיבה וכיצד היא משתנה עם הזמן. אפיגרפיה חוקרת את תוכן הכתובות והמידע ההיסטורי שיוצא מהן. כדאי לדעת: אות היא צורה מוסכמת. המשמעות היא שאנשים מסכימים איך לצייר אותה. לרוב הכתב משתנה לאט. אם מישהו מחליף כתב בכל מדינה, זה לא חלק מהפלאוגרפיה. כתב לפידארי (כתב לאבן): זהו ...
הבונה העסוק
בונה העסוק שואלת שאלה פשוטה: כמה עבודה יכולה מכונת טיורינג לעשות לפני שהיא עוצרת. מכונת טיורינג זה מחשב תיאורטי. זהו מכשיר עם סרט ארוך וראש קורא. המכונה קוראת ומושכת את הסרט. היא פועלת לפי טבלת הוראות. יש לה מצבים פנימיים. לפעמים המכונה לעולם לא עוצרת. S(n) אומרת את מספר הצעדים הכי גדול שמכונה עם ...
תורת הרקורסיה
תורת הרקורסיה בודקת מה מחשבים יכולים לחשב ומה לא. היא עוסקת בפונקציות שמקבלות מספר ומחזירות מספר. מכונת טיורינג היא מכונה דמיונית שעוברת על הוראות פשוטות. כל מכונה כזו אפשר למספר במספר טבעי. יש מכונות שמפסיקות ומחזירות מספר. יש כאלו שאף פעם לא עוצרות. לכן לפעמים פונקציה לא מוגדרת על כל הקלטים. אור...
טיפוס נתונים
טיפוס נתונים אומר אילו ערכים יכול משתנה לקבל. זה עוזר למחשב ולהמתכנת לדעת מה מותר לעשות. ברמת המחשב יש רק נתונים בזיכרון, לא טיפוסים. יש טיפוסים פשוטים: מספרים שלמים, מספרים עם נקודה (ממשיים), תווים ואמת/שקר. "תו" הוא סימן כמו אות או נקודה. "אמת/שקר" הם בדיוק שני ערכים: כן או לא. מספר שלם הוא מספ...
מספר חשיב
מספר חשיב הוא מספר שאפשר לחשב בעזרת תוכנה או מחשב מדומה. מכונת טיורינג היא מחשב תיאורטי. היא מוציאה ספרות של המספר אחת אחרי השנייה. אומרים שמספר הוא חשיב אם קיימת מכונה שמקבלת מספר n ומציגה את הספרות עד ה-n. אפשר לתת קירוב אחר: המכונה נותנת שבר שאומר כמה קרוב המספר האמיתי. הרבה מספרים חשובים ה...
רקורסיה
רקורסיה היא מצב שבו דבר אחד מכיל בתוכו עותק קטן של עצמו. אם יש נקודת עצירה, מפסיקים לחזור. אם לא, זה ממשיך לנצח. מראה מול מראה היא דוגמה פשוטה. הגדרה רקורסיבית היא הגדרה שמשתמשת בעצמה כדי להסביר את עצמה. תמונה שבתוכה יש את אותה התמונה שוב. קוראים לזה אפקט דרוסטה. צייר שצייר את התמונה שבה הוא מציי...
שיטת האב
שיטת האב היא דרך קצרה לדעת כמה זמן לוקח אלגוריתם שמחלק בעיות לבעיות קטנות. אלגוריתם רקורסיבי חוזר על עצמו על תת־בעיות. כדאי לזכור שלושה דברים שמשפיעים על הזמן: - כמה תת־בעיות יש (קוראים לזה a). - כמה קטנות הן התת־בעיות (קוראים לזה b). - כמה עבודה עושים בלי שוברים את הבעיה (קוראים לזה f(n)). אם ה...
הגדרה מעגלית
הגדרה מעגלית היא כשמגדירים מילה על ידי המילה עצמה. דוגמה: "הגדרה מעגלית היא הגדרה מעגלית". מקרה שלא מעגלי: "טלפון אלחוטי הוא טלפון הפועל ללא חוט". 'אלחוטי' אומר בלי חוט. יש דברים דומים: הסבר מעגלי אומר משהו בעזרת אותו הדבר. ההגיון המעגלי הוא נימוק שאומר את אותו הדבר שוב. דוגמאות קצרות: תשובה כי כך...
מספר משולשי ריבועי
מספר משולשי ריבועי הוא מספר שהוא גם ריבוע וגם משולש. ריבוע = מספר שמתקבל כאשר מרביצים מספר בעצמו. משולש = סכום של 1, 2, 3 ועוד. לדוגמה, 1 הוא כזה. גם 36 הוא כזה. אחר כך באים 1225 ו‑41616. יש חוק שחוזר שמייצר את המספרים הבאים מהשניים הקודמים. אלה מספרים מיוחדים כי הם מתאימים לשתי צורות שונות בו‑זמנ...
שפה טבעית
שפה טבעית היא השפה שאנשים מדברים בה. יש אלפי שפות ברחבי העולם. רוב השפות משתמשות בצלילים מהפה והגרון. יש גם שפות סימנים. שפות סימנים הן שפות בידיים. הן נוצרו בקהילות של אנשים שאינם שומעים. בעלי חיים מתקשרים, אבל לא בשפות אנושיות. בשפה יש מילים שמצביעות על מילים אחרות, כמו "הוא" שמצביע על שם. ניסו...