מכונת טיורינג הסתברותית
מכונת טיורינג הסתברותית היא רעיון של מחשב דמיוני. מחשב זה פועל עם קצת מזל. "הסתברות" כאן פירושה כמה סיכוי שמשהו יקרה. יש כמה דרכים לתאר את המכונה הזאת. כולן דומות למודל המכונה הרגיל, אבל מוסיפים אלמנט של מזל. במחשב רגיל קלט מקובל או נדחה ברור. במכונה ההסתברותית הדברים אינם ברורים לגמרי. אפשר לקבל ...
מכונת טיורינג
מכונת טיורינג היא רעיון שמסביר איך מחשב עובד בפשטות. אלן טיורינג המציא את הרעיון ב-1936. דמיין סרט ארוך מאוד עם תאים עליו. על הסרט זז ראש קטן. הראש קורא את התא, יכול לכתוב בו ולנוע ימינה או שמאלה. על הסרט יש קלט, וזהו המידע שהמכונה מקבלת. הראש קורא ומחליט מה לכתוב ואיפה לזוז לפי כללים פשוטים. ...
אלן טיורינג
אלן טיורינג נולד ב-1912 ונהיה למתמטיקאי חשוב. מתמטיקאי הוא אדם שעובד עם מספרים ורעיונות. הוריו עבדו בהודו והוא גדל בבריטניה. בבית הספר הוא אהב מתמטיקה. חבר קרוב שלו, כריסטופר, מת צעיר וזה השפיע עליו מאוד. טיורינג המציא רעיון שנקרא "מכונת טיורינג". זו דוגמה פשוטה שמראה איך מחשב יכול לחשב דברים. זו ...
הבונה העסוק
בונה העסוק שואלת שאלה פשוטה: כמה עבודה יכולה מכונת טיורינג לעשות לפני שהיא עוצרת. מכונת טיורינג זה מחשב תיאורטי. זהו מכשיר עם סרט ארוך וראש קורא. המכונה קוראת ומושכת את הסרט. היא פועלת לפי טבלת הוראות. יש לה מצבים פנימיים. לפעמים המכונה לעולם לא עוצרת. S(n) אומרת את מספר הצעדים הכי גדול שמכונה עם ...
תורת הרקורסיה
תורת הרקורסיה בודקת מה מחשבים יכולים לחשב ומה לא. היא עוסקת בפונקציות שמקבלות מספר ומחזירות מספר. מכונת טיורינג היא מכונה דמיונית שעוברת על הוראות פשוטות. כל מכונה כזו אפשר למספר במספר טבעי. יש מכונות שמפסיקות ומחזירות מספר. יש כאלו שאף פעם לא עוצרות. לכן לפעמים פונקציה לא מוגדרת על כל הקלטים. אור...
סיבוכיות מקום
סיבוכיות מקום אומרת כמה זיכרון צריך אלגוריתם. זיכרון זה הוא המקום בו הוא עושה חישובים, ולא המקום שבו שמים את הקלט. חוקרים משתמשים במודל פשוט שנקרא מכונת טיורינג. זו דמיון למחשב עם סרט ארוך שאפשר לקרוא ולכתוב. למדוד רק את "סרט העבודה" עוזר להעריך כמה זיכרון באמת צריך האלגוריתם. אם חזרו על אותו מצב ...
משפט סביץ'
משפט סביץ' הוכח ב־1970 על ידי וולטר סביץ'. המשפט מדבר על כמה זיכרון צריך מחשב כדי לפתור בעיות. מכונת טיורינג היא דרך לחשוב על מחשב פשוט. אם אפשר לפתור בעיה כשהמחשב "מנחש" (זה נקרא אי-דטרמיניזם), אז אפשר גם לפתור אותה בלי לנחש. אבל המחשב השני צריך יותר זיכרון. הכמות הנוספת היא כמו לקחת את הזיכרון ול...
אורקל (מדעי המחשב)
אורקל הוא קופסה שחורה שנותנת תשובות לשאלה בודדת בצעד אחד. קופסה שחורה הוא דבר שאפשר לשאול אבל לא לראות איך הוא עובד. אורקלים יכולים לפתור בעיות מאוד קשות, אפילו בעיות שלא תמיד אפשר לחשב, כמו בעיית העצירה (שאלה אם תוכנה תפסיק או תרוץ לנצח). מכונת טיורינג היא דרך לתאר מחשב פשוט בתור מודל. מכונת טיורי...
מספר חשיב
מספר חשיב הוא מספר שאפשר לחשב בעזרת תוכנה או מחשב מדומה. מכונת טיורינג היא מחשב תיאורטי. היא מוציאה ספרות של המספר אחת אחרי השנייה. אומרים שמספר הוא חשיב אם קיימת מכונה שמקבלת מספר n ומציגה את הספרות עד ה-n. אפשר לתת קירוב אחר: המכונה נותנת שבר שאומר כמה קרוב המספר האמיתי. הרבה מספרים חשובים ה...
תזת צ'רץ'-טיורינג
תזת צ'רץ'-טיורינג הוצעה על ידי אלן טיורינג ואלונזו צ'רץ' בשנות ה־30. היא אומרת: כל חישוב הגיוני אפשר לעשות עם מכונת טיורינג. מכונת טיורינג היא מכונה מדומיינת. היא קוראת וכותבת סימנים על סרט, בצעדים פשוטים. יש גרסאות שונות של התזה. גרסה חזקה מדברת על זמן ומשאבים. גרסה פיזיקלית אומרת שכל דבר שמערכת פ...
סיבוכיות
סיבוכיות היא מדד למספר המשאבים שמחשב צריך כדי לפתור בעיה. המשאבים העיקריים הם זמן (כמה זמן לוקח) וזיכרון (כמה מקום בתוכו). לפעמים בודקים גם כמה מחשבים קטנים עובדים ביחד. "בעיה" היא קבוצה של שאלות דומות. שאלה בודדת נקראת מופע. לדוגמה, בעיית הפירוק: למצוא את הגורמים של מספר. השאלה "למה 15 מתפרק?" היא...
מדעי המחשב
מדעי המחשב חוקרים איך מחשבים פועלים ומשתמשים בהם. הנושאים כוללים תכנות, אלגוריתמים (הוראות צעד־צעד לפתרון), ורשתות. הרעיון של מחשב קיים כבר מזמן. צ'ארלס בבג' תכנן מחשב מכני. עדה לאבלייס כתבה תוכנה למחשב שלו. במלחמות הפיתוח האיץ את המחקר. דוגמה היא אניגמה, מכונת הצפנה גרמנית. אלן טיורינג עזר לפצח...
אלגוריתם
אלגוריתם הוא סדרת צעדים ברורה לפתרון בעיה. זו כמו מתכון לעוגה. המתכון צריך לומר בדיוק מה לעשות. אם הוא לא ברור, ייתכן שיצטרכו לחשוב או לשמש שיפורים. אלגוריתם חייב לעצור בסוף ולתת תשובה נכונה. יש רעיון תאורטי בשם "מכונת טיורינג". זוהי מכונה דמיונית שמדגימה מה אפשר לחשב. יש בעיות שאי אפשר לפתור בכלל ...
חישוביות
תורת החישוביות עוסקת במה מחשבים ו"דגמים" דמיוניים יכולים לחשב. דגם חשוב נקרא מכונת טיורינג. זו דמות דמיונית של מחשב. השאלה הגדולה היא: מה אפשר לחשב ומה לא. יש בעיה שנקראת בעיית העצירה. משמעותה: אי אפשר תמיד לדעת אם תוכנית תעצור או תרוץ לנצח. בתחילת המאה ה-20 חוקרים רצו לדעת מהי דרך פשוטה לפתור בע...
מחשוב DNA
מחשוב DNA משתמש ב‑DNA במקום במחשב רגיל. DNA היא מולקולה שבה רשום המידע של יצורים חיים. חוקרים משתמשים ב‑DNA כדי לעשות חישובים כימיים. ב־1994 לאונרד אדלמן הראה ש‑DNA יכול לעזור למצוא דרכים ברשת של נקודות. זה היה הניסוי הראשון. בדוגמה אחרת, מדענים ב־2004 בנו ביו‑מחשב שיכול לזהות תאים חולים ולשחרר ת...
בעיית העצירה
בעיית העצירה שואלת: האם תוכנית תפסיק לרוץ על קלט מסוים? קלט הוא המידע שמכניסים לתוכנית. אלן טיורינג הראה ב-1936 שאין דרך כללית לבדוק את זה לכל תוכנית וקלט. מכונת טיורינג היא דגם רעיוני של מחשב. ההוכחה משתמשת ברעיון פשוט של סתירה. נניח שיש בודק Halt שמגיד אם תוכנית עוצרת על קלט. נבנה תוכנית A כך:...
תבנית:הידעת? 17 בספטמבר - סדרה 2
קטגוריה: מחשבים Ook! (אוּק) היא שפת תכנות. שפת תכנות = שפה שמלמדת את המחשב מה לעשות. היא משתמשת במילים של הברה אחת. שמה הגיע מהספרים של טרי פראצ'ט, 'עולם הדיסק'. Ook דומה לשפה שנקראת Brainfuck. זה מבוסס על רעיון של "מכונת טיורינג", רעיון שמסביר מה מחשבים יכולים לחשב. לכן אפשר לבצע בה חישובים רב...
סיבוכיות מעגלים
סיבוכיות מעגלים עוסקת במעגלים בוליאניים. מעגל בוליאני הוא רשת שערים לוגיים. שער לוגי הוא רכיב שמחליט על 0 או 1. AND מחזיר 1 רק אם כל הקלטים הם 1. OR מחזיר 1 אם לפחות קלט אחד הוא 1. NOT הופך 0 ל-1 ולהפך. למעגל יש כניסות ביטים ויציאה אחת. מעגלים מחוברים זה לזה כדי לחשב תשובה על קלט נתון. יש מעגלים ק...
ZPP
ZPP היא קבוצה של בעיות שמתקבלות על ידי אלגוריתם שאף פעם לא טועה. אלגוריתם הסתברותי עושה בחירות אקראיות, כמו הטלת מטבע. תוחלת זמן ריצה היא הזמן הממוצע שהאלגוריתם לוקח. בבעיות מסוימות יש פתרון מהיר שקובע תמיד את אותה תשובה. יש גם אלגוריתמים שמשתמשים באקראיות. חלקם יכולים לטעות לפעמים. ZPP שונה: הוא ת...
PP (מחלקת סיבוכיות)
PP היא קבוצה של בעיות שמחשבים עם מזל יכולים לפתור בזמן קצר. "מזל" כאן פירושו שהאלגוריתם עושה החלטות אקראיות. האלגוריתם עובד בכמות זמן שמתאימה לגודל הקלט. מחלקת PP אומרת: אם התשובה היא "כן", האלגוריתם צריך להגיד "כן" יותר מחצי מהפעמים. אם התשובה היא "לא", הוא לא אמור להגיד "כן" יותר מחצי מהפעמים. ...
משפט קוק-לוין
משפט קוק-לוין אומר שבעיה בשם SAT היא אחת הקשות בקבוצה שנקראת NP. P הן בעיות שאפשר לפתור מהר. NP הן בעיות שאם נותנים פתרון, אפשר לבדוק מהר אם הוא נכון. שאלה גדולה היא האם כל בעיה שאפשר לבדוק מהר אפשר גם לפתור מהר. זוהי שאלה פתוחה. SAT היא בעיה של נוסחאות לוגיות. נוסחאות אלה כתובות עם משתנים שאפ...
Ook!
Ook! היא שפת תכנות מוזרה ועקיצה. היא נועדה לכאורה לאורנגאוטנים. השפה משתמשת בשלוש מילים בלבד: "Ook.", "Ook?" ו־"Ook!". צירופים של המילים יוצרים פקודות. הפקודות נלקחות משפה אחרת בשם Brainfuck. Brainfuck היא שפה קטנה ומשונה. בגלל זה Ook! יכולה לעשות את כל מה שמחשב יכול לעשות (עקרון של מכונת טיורינג)....
אלגוריתם אקראי
אלגוריתם אקראי הוא תוכנה שמשתמשת במקריות. מקריות = משהו שקורה בלי דפוס, כמו הטלת מטבע. מחלקים את האלגוריתמים האקראיים לשתי קבוצות עיקריות. חוקרים שואלים אם אלגוריתמים אלה יכולים להיות מהירים יותר מאלגוריתמים רגילים. יש שתי קטגוריות חשובות: BPP ו‑P. BPP = בעיות שנפתרות מהר בעזרת מקריות. P = בעיות ש...
P (מחלקת סיבוכיות)
P היא קבוצה של בעיות שאפשר לפתור בצורה "מהירה" יחסית. "מהירה" כאן פירושו זמן פולינומי. זמן פולינומי אומר שהזמן גדל בצורה לא מוגזמת כשהקלט גדל. דוגמאות פשוטות ב-P הן חישוב המחלק המשותף הגדול של שני מספרים (GCD) ועץ פורש מינימלי. גם בדיקת האם מספר הוא ראשוני נכנסה ל-P בשנת 2002. בחירת זמן פולינומי ש...
Brainfuck
Brainfuck (או BF) היא שפת תכנות מיוחד ומצומצם. יש בה רק שמונה פקודות. היא הומצאה על ידי אורבן מילר בשנת 1993. היא נוצרה בשביל שעשוע והדגמה של פשטות. לשפה הזו כותבים תוכניות על רצועת תאים. משתמשים ב־+ ו־- כדי לשנות ערכים, וב־> ו־< כדי לעבור בין תאים. יש גם פקודות להדפסה וקלט. התכנות ב־BF קשה מאוד...
תורה אפקטיבית
תורה אפקטיבית היא תורה שאפשר לבדוק אם החוקים בה נכונים בעזרת מכונה. (מכונת טיורינג, סוג של מחשב תיאורטי.) בתורה יש אלפבית. אלפבית זה קבוצה קטנה של סימנים. טענות הן רצפים של סימנים מהאלפבית. יש אלגוריתם, הוראות ברורות, שבודק הוכחות. אם אין מכונה כזו, ייתכן שלא נוכל לבדוק אם ההוכחות בחוק נכונות....
משפט רייס
משפט רייס אומר שאי אפשר לכתוב תוכנית שתבדוק תכונות "מעניינות" של מה שתוכנית אחרת מחשבת. "מעניינות" כאן פירושו תכונה שמופיעה בחלק מהפונקציות, אבל לא בכולן. יש הוכחה שמראה שזה בלתי אפשרי. משתמשים ברעיון של פונקציה ריקה. פונקציה ריקה היא פונקציה שלא מחזירה שום דבר כי התוכנית שלה לא עוצרת. נניח שיש...