פורטל:מדעי המחשב/הידעת?/קטעי הידעת

לקט קטעי "הידעת?"

1	למת הניפוח היא שמן של שתי טענות עזר במדעי המחשב. למת הניפוח לשפות רגולריות מסייעת להראות ששפה פורמלית נתונה איננה שפה רגולרית. הטענה מציגה תנאי הכרחי לכך ששפה תהיה רגולרית; שפה שאינה מקיימת תנאי זה, איננה יכולה להיות רגולרית. באופן דומה, למת הניפוח לשפות חופשיות הקשר מסייעת להראות ששפה פורמלית נתונה איננה שפה חופשית הקשר. בישראל היא נקראת גם למת בר הלל, על שם יהושע בר-הלל.	עריכה | תבנית | שיחה
2	השאלה האם P=NP היא בעיה פתוחה מרכזית במדעי המחשב, העוסקת ביכולת לפתור אוסף גדול של בעיות בצורה יעילה. במילים פשוטות, השאלה היא האם כל בעיה שניתן לבדוק עבורה בצורה יעילה האם פתרון מוצע הוא נכון (בעיה השייכת לקבוצה NP), היא גם בעיה שניתן למצוא עבורה פתרון בצורה יעילה (בעיה השייכת לקבוצה P). לפתרון הבעיה ישנן השלכות תאורטיות ומעשיות רבות, והיא זכתה להכרה כאחת מ"שבע בעיות המילניום" של מכון קליי למתמטיקה. אף שכיום לא ידועה תשובה לשאלה זו, ההשערה הרווחת היא כי P≠NP. השאלה האם P=NP אינה בעלת ערך אקדמי בלבד. עם התפתחות השימושים המסחריים של ההצפנה בעידן המחשב, ובמיוחד במסחר אלקטרוני, הפכה התשובה לשאלה לבעלת חשיבות כלכלית לא מבוטלת. הסיבה לכך היא שרוב המסחר האלקטרוני ותעשיית האבטחה הדיגיטלית מסתמכים על אלגוריתמים שיכולת ההצפנה שלהם נובעת מחוסר היכולת הנוכחי לפתור בעיות NP בזמן סביר.	עריכה | תבנית | שיחה
3	משפט רייס הוא משפט מרכזי בתחום החישוביות, שעוסק ביכולת של אלגוריתמים לחקור אלגוריתמים אחרים. המשפט קובע שאין תוכנית מחשב שמקבלת כקלט תוכנית מחשב אחרת, ומכריעה האם הפונקציה שמחשבת תוכנית מחשב זו היא בעלת תכונה מסוימת "לא-טריוויאלית" או לא. (כלומר, תכונות אשר מאפיינות חלק מהפונקציות שמחושבות בידי תוכנית מחשב, אך לא את כולן) יש לשים לב שהתכונה היא תכונה של הפונקציה, ולא של תוכנית המחשב עצמה. באופן אינטואיטיבי המשפט טוען שתוכנית מחשב אינה יכולה לדעת מה תוכנית מחשב אחרת עושה (כי אז היא הייתה צריכה להריץ אותה, וזה שקול לבעיית העצירה).	עריכה | תבנית | שיחה
4	אלגוריתם הוא דרך שיטתית (כלומר כזו שצעדיה מוגדרים היטב) לביצועה של משימה מסוימת במספר סופי של צעדים. מקור המלה בשמו של המתמטיקאי מוחמד אבן מוסא אל-ח'ואריזמי, שחי בבגדאד במאה התשיעית. כאשר ספרו על שיטות חישוב תורגם ללטינית, נכתב שמו של אל ח'ואריזמי כ"אלגוריטמי", והקוראים טעו לחשוב שמדובר בצורת רבים של המושג שיטת חישוב.	עריכה | תבנית | שיחה
5	סיבוכיות קולמוגורוב מוגדרת כאורך תוכנית המחשב הקצרה ביותר המייצרת טקסט מסוים. לטקסט שבלוני, חדגוני וצפוי, תהיה סיבוכיות קולמוגורוב נמוכה, בעוד שלטקסט מורכב, חדשני ומפתיע, תהיה סיבוכיות קולמוגורב גבוהה. בשביל להמחיש את הרעיון, ניתן לחשוב על המחרוזת הבאה: 001001001001001001001001001001 מבחינת הסיבוכיות האלגוריתמית, זוהי מחרוזת פשוטה (בעלת סיבוכיות קטנה) מכיוון שהתוכנית המייצרת אותה היא פשוט לולאה הפועלת עשר פעמים ומדפיסה: 001. לעומת זאת, המחרוזת הבאה היא כנראה יותר מסובכת: 00111100111000111000111110101101101 מכיוון שלא ניכר כלל פשוט המייצר אותה.	עריכה | תבנית | שיחה
6	שפת התכנות Ook!‎ (אוּק) מבוססת על אוצר מילים בן הברה אחת, והיא נקראת כך בעקבות אוצר המילים של הספרן האורנגאוטן בסדרת ספרי הפנטזיה "עולם הדיסק" מאת טרי פראצ'ט. שפה זו שקולה לשפת Brainfuck, המהווה מימוש ישיר של מכונת טיורינג, ולכן, למרות פשטותה, מסוגלת לבצע כל חישוב או אלגוריתם שהוא בר ביצוע במחשב כלשהו.	עריכה | תבנית | שיחה
7	שפת B היא שפת תכנות שהייתה אחת משפות התכנות העיליות הראשונות. השפה פותחה במעבדות בל, ומכאן ה-B שבשמה. שפת C, שבגרסאות אחדות שלה משתמשים עד היום, נכתבה בשפת B, וקיבלה את ההשראה לשמה משפה זו: שפה המתקדמת צעד אחד הלאה משפת B. כאשר התפתחה שפת C, נכתב המהדר של השפה בשפת C עצמה, תהליך הנקרא Bootstrapping.	עריכה | תבנית | שיחה
8		עריכה | תבנית | שיחה
9	מחשב קוונטי הוא מחשב המבצע עיבוד נתונים על "ביטים קוונטים" - qubits ומשתמש בתכונות של מכניקת הקוונטים על מנת לבצע עיבוד נתונים יעיל יותר. המחשב הקוונטי מבוסס על אכסון של קיוביטים ופעולה עליהם, באנלוגיה למחשב קלאסי הפועל על ביטים. השוני בין השניים, ומקור הכוח הנוסף של המחשב הקוונטי, נובעים מתופעות הסופרפוזיציה והשזירה המתקיימות עבור קיוביטים. למרות שידועות בעיות שמחשב הקוונטי יכול לפתור ביעילות גדולה יותר ממחשב קלאסי, יכולתו של מחשב קוונטי אינה בלתי מוגבלת והוא אינו "פתרון קסם" לכל בעיה חישובית. בראש ובראשונה, ידוע כי ההבדל העקרוני בין מחשבים קוונטיים וקלאסיים הוא ביעילות (דהיינו, סיבוכיות) בלבד; כלומר, כל בעיה הניתנת לפתרון על מחשב קוונטי ניתנת לפתרון גם על כל מחשב קלאסי, אם כי ייתכן שהדבר ידרוש משאבים גדולים יותר. גם הפרש היעילות אינו שרירותי - הוא לכל היותר מעריכי, וישנן בעיות אותן מחשב קוונטי אינו יכול לפתור באופן יעיל הרבה יותר ממחשב קלאסי. לא ידוע אם מחשב קוונטי מסוגל לפתור בעיות NP-שלמות בזמן ריצה פולינומי, ומדענים רבים משערים שאין כך הדבר.	עריכה | תבנית | שיחה
10	e הוא מספר טרנסצנדנטי וקבוע מתמטי חשוב בעל שימושים רבים באנליזה מתמטית, ומשמש כבסיס הלוגריתם הטבעי, אם כי אינו מוכר כמו π. גרסאות תוכנת Metafont ממוספרות במספרים 2, 2.7, 2.71, וכן הלאה, כך שילכו ויתקרבו ל-e. רעיון המספור על פי מספר אוילר הוא פרי מוחו של ממציא התוכנה, מדען המחשב דונלד קנות', שנחשב "משוגע לדבר".	עריכה | תבנית | שיחה
11	פרס לובנר הוא תחרות שנתית בין בוטי שיחה שבה זוכה הבוט שנחשב לאנושי ביותר באותה שנה. התחרות נערכת במתכונת דומה למבחן טיורינג. כלומר, על הבוט לשכנע אנשים המתכתבים איתו כי הוא מדבר עם אדם אמיתי. את הענקת הפרס יזם בשנת 1990 ד"ר יו לובנר יחד עם מרכז קיימברידג' למחקרים התנהגותיים. הבוט הראשון שהשופטים לא יצליחו להבחין בינו לבין אדם במבחן טיורינג שכולל גם פענוח והבנת טקסט, תמונות ושמע, יגרוף פרס על סך 100,000 דולר ומדליית זהב; אז גם התחרות תפסיק להתקיים. הפרס שנוי במחלוקת בקרב העוסקים בבינה מלאכותית. מרווין מינסקי, מחלוצי הבינה מלאכותית האשים את לובנר וטען נגדו שהוא יצר מסע פרסום שנתי מגונה וחסר תועלת, ובבדיחות הציע את "פרס מינסקי" בסך 100 דולר לאדם שישכנע את לובנר להפסיק את התחרות. לובנר טען בתגובה כי מי שיצליח לזכות במדליית הזהב יגרום להפסקת התחרות, ויהיה זכאי גם לפרס מינסקי, ועל כן רואה לובנר במינסקי נותן חסות לתחרות.	עריכה | תבנית | שיחה
12	BPP (ראשי תיבות של Bounded-Error, Probabilistic, Polynomial Time) הינה מחלקת הבעיות שיש עבורן אלגוריתם אקראי עם זמן ריצה פולינומי, אשר צודק בהסתברות "טובה": האלגוריתם יענה את התשובה הנכונה בהסתברות לפחות ε+½. המחלקה נחשבת כזו שמיצגת באופן הטוב ביותר את הבעיות שלהן יש אלגוריתם סביר. המחלקה BPP מכילה את מחלקות הסיבוכיות RP ו-Co-RP, אשר מאפשרות טעות חד-צדדית בלבד, וכמובן את מחלקת הסיבוכיות P, אשר אינה מאפשרת אקראיות בכלל (ולכן, ממילא, האלגוריתם חייב לצדוק תמיד).	עריכה | תבנית | שיחה
13	באג הוא תקלה במחשב שמקורה בתוכנה שנכתבה בצורה פגומה, מתכנון לקוי של האלגוריתם או מטעות בשלב התכנות. השימוש במונח ה"באג" לתיאור של פגמים בלתי מוסברים הוא חלק מהמינוח המקצועי בעולם ההנדסה כבר מהמאה ה-19, והיה בשימוש מהנדסי מכונות לתיאור של כשלים מכניים. בעיות באלקטרוניקה של מכשירי מכ"ם במהלך מלחמת העולם השנייה נודעו כבאגים (או גליצ'ים). טביעת המושג משויכת בטעות לגרייס הופר, שפרסמה את הסיבה לתקלה במחשב אלקטרומכני מוקדם. גרסה אופיינית לסיפור מופיעה בציטוט הבא: ב-1946, כשהופר שוחררה משירות פעיל, היא הצטרפה לסגל הרווארד במחלקה למיחשוב, שם המשיכה בעבודתה על מארק II ומארק III. מפעילים שעקבו אחרי תקלה במארק II מצאו עש שנלכד באחד הממסרים (relay), והשתמשו במושג "באג". העש הוסר בזהירות והודבק לדף הלוג של ה-9 בספטמבר 1945. בעקבות אותו באג ראשון אנו נוהגים להתייחס לתקלות או גליצ'ים כבאגים. — Danis, Sharron Ann: "Rear Admiral Grace Murray Hopper"‎ הופר איננה זאת שמצאה את החרק, כפי שהיא בעצמה מודה, והתאריך לא היה 1945 אלא 9 בספטמבר 1947. אף שברור כי מפעילי מארק II לא טבעו את המונח באג, נטען שהם המציאו את המונח debug (ניפוי).	עריכה | תבנית | שיחה
14	משפט ארבעת הצבעים הוא תוצאה בולטת בתורת הגרפים. לפי המשפט, אפשר לצבוע כל מפה מדינית, באופן שכל שתי מדינות בעלות קו גבול משותף נצבעות בצבע שונה, תוך שימוש בארבעה צבעים בלבד. בניסוח מודרני, המשפט מבטיח שלכל גרף מישורי קיימת צביעת קודקודים בארבעה צבעים. בשנת 1976 וולפגאנג האקן וקנת אפל מאוניברסיטת אילינוי הראו שכל מפה אפשרית שקולה לאחת מבין 1,936 מפות שונות. לאחר מכן הם הריצו תוכנית מחשב במשך 1,200 שעות כדי להראות שכל אחת ממפות אלה ניתנת לצביעה בארבעה צבעים. זו הייתה ההשערה המפורסמת הראשונה שהוכחה בעזרת מחשב, ובתחילה לא הייתה הסכמה כללית על תקפות ההוכחה, בעיקר בנימוק שלא הוכחה נכונותן של תוכניות המחשב עצמן. מאז נעשו ניסיונות רבים למצוא הוכחה סטנדרטית יותר, שיכולה לעמוד לביקורת עמיתים. הוכחה כזו עדיין לא נמצאה. בשנת 1996 ניתנה הוכחה דומה, שבה היה די בבדיקה של 663 מפות. גם בדיקה זו דרשה הסתייעות במחשב.	עריכה | תבנית | שיחה
15	נועם חומסקי הוא פרופסור לבלשנות במכון הטכנולוגי של מסצ'וסטס (MIT), הוגה דעות אנרכיסט, פעיל למען זכויות אדם ופרשן פוליטי המזוהה עם השמאל הרדיקלי. בעבודתו האקדמית הוא מייסד אסכולת הבלשנות הגנרטיבית, והוגה היררכיית חומסקי, שהיא שיטת מיון של שפות פורמליות. ההיררכיה שהוא הציע מחלקת דקדוקים פורמליים לקבוצות על פי כוח הבעה עולה. כלומר, כל קבוצה עוקבת יכולה ליצור מערך רחב יותר של שפות פורמליות מזו שקדמה לה. לטענתו של חומסקי, מודליזציה של הבטים מסוימים בשפה טבעית דורשת דקדוק פורמלי מורכב יותר (כפי שהוא נמדד בהיררכיית חומסקי) מאשר מודליזציה של שפות אחרות. לדוגמה, בזמן ששפה רגולרית חזקה מספיק לתאר מורפולוגיה אנגלית, היא אינה חזקה מספיק כדי לתאר תחביר אנגלי. בנוסף להיותה רלוונטית לבלשנות, היררכיית חומסקי נעשתה חשובה במדעי המחשב, ויש לה קשרים חשובים גם לתורת האוטומטים.	עריכה | תבנית | שיחה
16	תערו של אוקאם הוא עיקרון פילוסופי המיוחס לוויליאם איש אוקאם, נזיר פרנציסקני אנגלי בן המאה ה-14. תערו של אוקאם מהווה כלל מנחה בעת מציאת הסבר לתופעות בתחומים שונים. על פי כלל זה, כאשר קיימים הסברים שונים לאותה תופעה, יש לבחור את הפשוט ביותר, אשר מערב את המספר המועט ביותר של מושגים. שפת התכנות אוקאם (OCCAM) היא שפה עילית שפותחה על ידי INMOS, ושתוכננה במיוחד כדי לבטא אלגוריתמים מקביליים ואת יישומם ברשת של מעבדים. היא בנויה על העיקרון המינימליסטי של אוקאם, כלומר נמנעת מכפילות של מנגנונים בשפה שלא לצורך.	עריכה | תבנית | שיחה
17	משתנה (variable) הוא חלק זיכרון בתוכנית המכיל נתון שיכול להשתנות בזמן הריצה, על פי הפקודות הניתנות לו, בניגוד לקבוע שמכיל ערך שנקבע בתחילת ההרצה ונשאר קבוע עד סופה. לכל משתנה יש טיפוס שקובע איזה סוג נתונים הוא יכול להכיל. גודל המשתנה שונה בהתאם לטיפוס ויכול לנוע מבַּיִת אחד ועד טווח זיכרון גדול של מגהבייטים שלמים. בחלק משפות התכנות כמו שפת C ושפת Pascal, חובה להכריז על המשתנה לפני השימוש בו. שימוש במשתנה בלי הכרזה מפורשת שלו תגרום להודעת שגיאה. שפות אחרות, בעיקר שפות סקריפט כמו VBScript לא דורשות מן התוכניתן להכריז על המשתנה בטרם השימוש בו, והמערכת מגדירה אותו בפעם הראשונה שהיא נתקלת בו. הטווח שבו המשתנה קיים פיזית נקרא אורך החיים של המשתנה. משתנה גלובלי יהיה קיים כל זמן שהתוכנה רצה. משתנה לוקאלי המוגדר בפונקציה יהיה קיים בזמן שהפונקציה מורצת, אך לפניה או אחריה הוא לא יהיה קיים כלל.	עריכה | תבנית | שיחה
18	-	הוספה
19	העיר קניגסברג שבפרוסיה המזרחית (כיום קלינינגרד שברוסיה) הייתה מחולקת לארבעה חלקים על ידי הנהר פרגוליה. שבעה גשרים חיברו בין ארבעת חלקי העיר. בין תושבי העיר התפתחה מסורת לפיה לא ניתן לחצות את כל שבעת הגשרים ולחזור לנקודת ההתחלה מבלי לעבור על אותו גשר יותר מפעם אחת. תושבי העיר ניסו להוכיח או להפריך השערה זו, אולם ללא הצלחה. הבעיה התפרסמה בשם בעיית הגשרים של קניגסברג. המתמטיקאי לאונרד אוילר הצליח לפתור את הבעיה, והציג את פתרונו לאקדמיית סנקט פטרבורג ב-26 באוגוסט 1735. בהוכחתו הוא תיאר את הבעיה באופן סכמטי: כל נקודה ייצגה חלק של העיר, וכל קו ייצג גשר. הוא הראה שמכיוון שמכל נקודה יוצא מספר אי-זוגי של קווים, לא קיים מסלול סגור שעובר דרך כל הקווים. הייתה זו אחת הבעיות הראשונות בתורת הגרפים שנפתרו.	עריכה | תבנית | שיחה
20	קודגורו היא תחרות מחשבים ישראלית לעידוד המצוינות במדעי המחשב הנערכת במרכז הבינתחומי הרצליה. התחרות התקיימה לראשונה בשנת 1999 ומתקיימת מאז ברציפות מדי שנה. קהל היעד הוא בני 15 עד 18 (התחרות פתוחה לכל מי שטרם מלאו לו 19 שנה ביום התחרות עצמו). התחרות נועדה לאתר בני נוער בעלי יכולות גבוהות במיוחד ולסייע להם להתקדם בתחומים אלה. הספונסרים של התחרות מגיעים מהגופים הבולטים במשק בתחום האקדמיה, התעשייה והצבא ומאפשרים לתת לתחרות ולמשתתפים ערך מוסף בדמות שיתופי פעולה עם המשתתפים וליווי שלהם לאחר התחרות. הפרסים לתחרות הם ציוד מחשוב מתנת חברת יבמ ישראל.	עריכה | תבנית | שיחה
21	-	הוספה
22	הצפנה קוונטית משתמשת במכניקה קוונטית לאבטחת ערוץ תקשורת. בניגוד לקריפטוגרפיה מסורתית, המיישמת טכניקות מתמטיות כמו הצפנה סימטרית ומפתח פומבי כדי להסתיר את תוכן המידע מפני מצותת, הצפנה קוונטית מתבססת על חוקים פיזיקליים מתורת הקוונטים כמו עיקרון אי הוודאות של הייזנברג, סופרפוזיציה ושזירה קוונטית, הבאים לידי ביטוי בהתנהגות פוטונים (חלקיקי אור), כדי ליצור ערוץ תקשורת בטוח שאינו ניתן בשום אופן לציתות מבלי להפריע לשידור. חוקי הפיזיקה מגנים על הערוץ אפילו מפני מצותת בעל עוצמת חישוב בלתי מוגבלת	עריכה | תבנית | שיחה
23	-	הוספה
24	חמישה מדעני מחשב ישראלים זכו בפרס טיורינג: בשנת 1976: מיכאל רבין מהאוניברסיטה העברית (יחד עם דנה סקוט), על מאמרם העוסק באוטומטים סופיים, שהציג את הרעיון של מכונות לא דטרמיניסטיות. בשנת 1996: אמיר פנואלי ממכון ויצמן למדע, על עבודתו המקורית להבאת לוגיקה טמפורלית למדעי המחשב ועל תרומתו לאימות תוכנה. בשנת 2002: עדי שמיר ממכון ויצמן למדע (יחד עם רונלד ריבסט ולאונרד אדלמן), על תרומתם לפיתוח הצפנה במפתח ציבורי. בשנת 2011: יהודה פרל מאוניברסיטת קליפורניה בלוס אנג'לס, על תרומה יסודית לחקר בינה מלאכותית באמצעות פיתוח תחשיב להסקה סיבתית והסתברותית. בשנת 2012: שפי גולדווסר מהמכון הטכנולוגי של מסצ'וסטס וממכון ויצמן למדע (יחד עם סילביו מיקאלי) על תרומה יסודית לביסוס הסיבוכיות התאורטית של הצפנה ופיתוח שיטות יעילות לאימות הוכחות מתמטיות בתורת הסיבוכיות.	עריכה | תבנית | שיחה
25	היחס בין מדעי המחשב להנדסת תוכנה הוא נושא הנתון במחלוקת מתמשכת. יש המצדדים בגישה הטוענת שהנדסת תוכנה היא ענף משני של מדעי המחשב. לעומתם, יש הטוענים שהמיקוד העיקרי של מדעי המחשב הוא לימוד וגילוי אמיתות כלליות בתחום החישוביות, ואילו הנדסת תוכנה מתמקדת בתכנון ויישום מקרים פרטניים של בעיות חישוביות, להשגת מטרה מעשית. תומך מובהק בגישה זו הוא דייוויד פרנס. בין הנדסת תוכנה למדעי המחשב יש חפיפה רבה בתחומי האלגוריתמיקה והאימות. עם זאת, מדעי המחשב נוטים למחקר תאורטי בתחומים אלה, ואילו הנדסת תוכנה נוטה לצד המעשי, ושמה דגש על פתרון של בעיות בקנה מידה גדול ותעשייתי.	עריכה | תבנית | שיחה
26	במסגרת פרס נובל לא נכלל פרס למדעי המחשב, שהתפתחו שנים רבות לאחר שהוחל, בשנת 1901, בהענקת פרס נובל. למדעי המחשב נוסד בשנת 1966 פרס יוקרתי משלהם, פרס טיורינג. הרברט סיימון, חוקר יהודי-אמריקאי בולט בתחומי הפסיכולוגיה, הכלכלה והניהול, מדעי המחשב ופילוסופיה של המדע, הוא האדם היחיד שזכה בשני הפרסים גם יחד: פרס טיורינג בשנת 1975 ופרס נובל לכלכלה בשנת 1978.	עריכה | תבנית | שיחה
27	קטע הקוד השנוי במחלוקת קועקע על זרוע מפגין בעוד חוקי הייצוא של ארצות הברית אוסרים על יצוא נשק ואמצעי הצפנה חזקים, ייצוא של ספרים אינו יכול להיות מוגבל, עקב חופש הדיבור המעוגן בחוקה. בשנת 1993 נפתחה חקירה פלילת כנגד פיל צימרמן בעילה שהפצת תוכנת ההצפנה PGP שפיתח ופרסם ברשת היוזנט, הינה עברה על חוקי הייצוא. כתגובה לכך, פרסם צימרמן ספר, שהכיל הדפסה של קוד המקור של תוכנת PGP. על ספר זה לא קיימת הגבלת ייצוא, וכל אדם החפץ בתוכנה יכול היה לסרוק את דפי הספר ובכך לטעון את התוכנה אל מחשבו. חוקי ייצוא הצפנה בארצות הברית עדיין קיימים, אך עברו שינוי מהותי במהלך שנות ה-90 לאור מקרה זה, וכיום ניתן להפיץ תוכנה הכוללת הצפנה בצורה קלה יחסית.	עריכה | תבנית | שיחה
28		עריכה | תבנית | שיחה
29	המחקר התאורטי של יכולותיהם של מחשבים קדם למימוש הפיזי שלהם. ב-1931 הוכיח קורט גדל את משפטי האי-שלמות של גדל, צעד הנחשב כיום כערש מדעי המחשב התאורטיים. במהלך ההוכחה של המשפטים מגדיר גדל לראשונה את הפונקציות הניתנות לחישוב הבסיסיות ומראה כיצד ניתן "לתכנת" בעזרתן פונקציות מתקדמות יותר. ב-1936 הציג אלן טיורינג את מכונת טיורינג, מודל מתמטי מופשט המדמה את פעולת המחשב. טיורינג הוכיח בלכסון שמכונות טיורינג אינן מסוגלות לפתור את בעיית העצירה. לפי תזת צ'רץ'-טיורינג למכונות טיורינג כוח חישובי דומה לזה של כל מחשב קיים, ומכאן שאף מחשב אינו מסוגל לפתור את בעיית העצירה. טיורינג גם תרם לפן המעשי של מדעי המחשב, כאשר פיתח את מכונת הבומב ששימשה לפיצוח האניגמה - הצופן של גרמניה הנאצית במלחמת העולם השנייה. כיום הענפים העוסקים ביכולותיהם ובמגבלותיהם של מחשבים קרויים תורת החישוביות ותורת הסיבוכיות.	עריכה | תבנית | שיחה
30	-	הוספה

בחזרה לפורטל