ישנן שתי בעיות עיקריות באימות תוכנה. המעשית שבהן היא שאימות תוכנה דורש מיומנות רבה ורקע מתמטי ברמה גבוהה מהמקובל. הבעיה החמורה יותר היא שלא ניתן להוכיח קיום או שלילה של תכונה כלשהי על כל תוכנית שרירותית. דוגמה לכך היא ההוכחה כי אי אפשר לפתח תוכנית שיכולה לוודא האם תוכנית כלשהי תעצור כאשר תקבל קלט מסוים (בעיה זו ידועה כבעיית העצירה). משפט רייס מוכיח כי לא ניתן לכתוב תוכנית שתוכל להכריע לגבי כל תוכנית שהיא האם היא מקיימת תכונה לא טריוויאלית (תכונה שלא כל תוכנית בהכרח מקיימת) כלשהי.
למרות שמגבלה תאורטית זו נראית חמורה עדיין אימות תוכנה תורם רבות מבחינה מעשית. בפרט, ניתן "ללכת על בטוח", להגיד שתוכנית תקינה רק כאשר היא תקינה בוודאות, ולטעות על חלק מהתוכניות התקינות. גישה כזאת נקראת "שמרנית". דוגמה לכך היא מערכת טיפוסים בשפות תכנות, המוכיחות היעדר של שגיאות טיפוסים.
אמיר פנואלי ממכון ויצמן למדע היה למומחה ברמה בינלאומית בתחום זה ואף זכה על מחקריו בתחום בפרס טיורינג, הפרס החשוב ביותר במדעי המחשב, על מחקרו ופיתוחיו בתחום הלוגיקה הטמפורלית.
חישוביות
תורת החישוביות היא הבסיס למדעי המחשב, והיא עוסקת במודלים לחישוב ובפונקציות הניתנות לחישוב במסגרתם. השאלה הבסיסית בתורת החישוביות היא: מה מחשבים יכולים לחשב, ומה לא? בניגוד להנחה נפוצה, ישנן פונקציות שאי אפשר לחשב. בעיית העצירה מהווה דוגמה לפונקציה שכזו: ניתן להוכיח כי אין תוכנית היכולה לקבל כקלט תוכנית כלשהי וקלט לאותה התוכנית, ולהכריע האם התוכנית תעצור.
למעשה, מספר הפונקציות שניתן לחשב הוא formula_1 (קרי: אָלֶף אֶפֶס), מאחר שלכל בעיה חשיבה ניתן לכתוב תוכנית מחשב, ומספר תוכניות מחשב שאנחנו יכולים לכתוב הוא formula_1. מאידך, מספר הבעיות החישוביות כולן הוא formula_3 (ז"א, מעוצמת הרצף). לכן, רק מהשוואת עוצמות, ניתן להסיק שבהכרח קיימות בעיות חישוביות אשר לא ניתנות לפתרון תחת מודלים חישוביים מסוימים, כדוגמת מכונת טיורינג.
היסטוריה.
תורת החישוביות החלה להתפתח בתחילת המאה ה-20, במחקרים מתמטיים שעסקו בשאלה אילו בעיות מתמטיות ניתן לפתור בדרכים פשוטות. ראשית היה צריך לקבוע מהי "דרך פשוטה", ולשם כך היה צורך במודל של חישוב. אחד המודלים הראשונים שנוצרו הוא מכונת טיורינג, שנקראת על שם ממציאה אלן טיורינג, אשר מהווה אבן דרך בתורת החישוביות כולה, בשל פשטותו ודמיונו למחשב (שטרם הומצא בעת יצירת מודל זה). מודל אחר הוא זה של תחשיב למדא. הוכח ששני מודלים אלה, ומודלים רבים נוספים אחרים שהוצעו (כגון דקדוקים בלתי מוגבלים), שקולים זה לזה בכוחם החישובי - חישוב שניתן לבצע באחד מהמודלים ניתן לבצע גם באחרים. מודלים אלה שקולים גם למחשב, אם נניח קיומו של זיכרון בלתי מוגבל בגודלו. תזת צ'רץ'-טיורינג משערת שכל פורמליזציה סבירה של מושג האלגוריתם תהיה שקולה למכונת טיורינג.
הנושא של חישוביות עלול להיראות זר, כי אכן יש הנחה שגויה שכל פונקציה ניתן לחשב, אך למעשה, פונקציה היא מונח מתמטי שמתאר התאמה בין ערכים (גם אם לא ניתן להביע התאמה זו בדרך קומפקטית כלשהי או בתהליך חישובי אלא רק בטבלה אינסופית) ואילו אלגוריתם הוא תהליך שעבור כל קלט תקין, מניב את ערך התמונה של הפונקציה.
הגילויים אודות הפער בין פונקציות לפונקציות חשיבות, מצטרפים לגילויים דומים (למעשה אותו גילוי ממש) כמו משפט אי השלמות של גדל.
גם כיום נחשבת תורת החישוביות לנושא מחקר עיקרי בפקולטות למדעי המחשב. קורסי מבוא על תורת החישוביות ניתנים כקורסים מתקדמים לתואר ראשון במדעי המחשב ומתמטיקה.
תחומי המחקר ומונחי יסוד.
את מחלקת השפות (בעיות) שניתנות להכרעה למחצה, דהיינו, שניתן לבנות מכונת טיורינג שתמיד מקבלת קלט שהוא בשפה (גם אם אינה עוצרת על קלט שאינו בשפה), מסמנים ב-RE (Recursivley enumerable). באופן שקול, מגדירים את המחלקה coRE, כמחלקת השפות שניתן לחשב את דחייתן - כלומר, שעבור כל קלט ניתן לודא שהוא אינו בשפה. אם כן, כל שפה שהיא חשיבה נמצאת בחיתוך של RE ו-coRE.
במסגרת תורת החישוביות נבחנות תכונותיהם של מודלים חישוביים שונים, על ידי בדיקת מחלקת הפונקציות שניתן לחשב במודל, ושקילותה למחלקת הפונקציות של מודל אחר. ההיררכיה של חומסקי מתארת היררכיית מחלקות הניתנות לחישוב במודלים שונים, כך שלכל מחלקת פונקציות בהיררכיה מתאימים מודלים רבים, השקולים זה לזה. למשל, דקדוקים חופשיי הקשר שקולים לאוטומטי מחסנית, מבחינה זו, והאוטומטים הסופיים שקולים לדקדוקים ליניאריים ימניים. במסגרת היררכיה זו מתקיימים גם השוויונות שתוארו לעיל, בין תחשיב למדא, מכונת טיורינג, והדקדוקים הבלתי מוגבלים.
בנוסף, ניתן לחקור תכונות כלליות של מחלקות של פונקציות. למשל, מחלקות פונקציות שהן פונקציות פרימיטיביות רקורסיביות, והקשר בינן לבין מחלקות אחרות.
תחומי מחקר משיקים.
גם כאשר בעיות ניתנות לחישוב, ייתכן שהן דורשות זמן כה רב להשגת הפתרון עד שהפתרון חדל להיות מעשי - בסוגיה זו עוסקת תורת הסיבוכיות.
.F.B.I (באנגלית: Federal Bureau of Investigation - לשכת החקירות הפדרלית; ידועה בעברית גם כבולשת הפדרלית בארצות הברית) היא גוף המסונף למחלקת המשפטים של ארצות הברית, הפועל לחקירת פשעים פדרליים וכן מהווה סוכנות ריגול הפועלת לאיסוף מידע על פעולות חתרנות, טרור וריגול המתרחשות בתוך ארצות הברית בניסיון לערער את קיומה. ל-FBI יש סמכות לפעול ביותר מ-2000 עבירות על החוק הפדרלי. המוטו של ה-FBI הוא: "אמינות אומץ ויושרה" שמהווה פירוש נוסף לראשי התיבות המרכיבים את שמו (Fidelity, Bravery, Integrity).
בניין המפקדה הראשית, בניין ג'יי אדגר הובר, ממוקם בוושינגטון די. סי. ובו גם מעבדת זיהוי פלילי מן המתוחכמות בעולם. 56 מפקדות נוספות פזורות בערים ראשיות רבות ברחבי ארצות הברית, ועוד מעל 400 נציגויות בערים קטנות יותר. כמו כן ללשכה יותר מ-50 משרדים בינלאומיים הממוקמים בשגרירויות ארצות הברית ברחבי העולם.
פעילות הלשכה.
בשנת 2014 תקציב הלשכה היה 8.3 מיליארד דולר לכל הפחות, הכוללים גם 618 מיליון דולר שנועדו לפעילויות של מלחמה בטרור, פשעי אינטרנט, מעקבים, נשק להשמדה המונית, פשעי צווארון לבן ותוכניות הכשרה.
ה-FBI נוסד בשנת 1908 בשם BOI (הלשכה לחקירות, Bureau of Investigation). שמו שונה ל-FBI בשנת 1935. מטרתו העיקרית של ה-FBI היא להגן על ארצות הברית מפני טרור ואיומים זרים, לקיים ולאכוף את החוקים הפליליים של ארצות הברית ולספק הנהגה וצדק מוסרי לפדרציה האמריקנית, למדינות, לערים ולסוכנויות בינלאומיות.
נכון להיום פעילותו העיקרית של ה-FBI היא:
באוגוסט 2010 חקירת ה-FBI טיפלה בנושאים אלה בעיקר:
השמורות האינדיאניות.
בסמכות הממשל הפדרלי בארצות הברית לחקור ולתבוע במקרים של פשעים חמורים המתרחשים בשמורות האינדיאניות.
היסטוריה.
הלשכה לחקירות - .B.O.I.
בשנת 1908 הוקמה "הלשכה לחקירות" (BOI - Bureau of Investigations), גוף פדרלי שטיפל בנושאים שונים של אכיפת חוק.
בשנת 1921 מונה ג'. אדגר הובר כסגן המנהל של "הלשכה לחקירות". באותה עת הייתה הלשכה לחקירות גוף חסר שיניים, וסמכויותיה היו מועטות. 650 אנשיה (מתוכם 441 סוכנים הפזורים ברחבי ארצות הברית) לא נשאו נשק ולא היו להם סמכויות מעצר. בשנת 1924 מונה הובר לעמוד בראש הלשכה.
בשנת 1929 הכה בארצות הברית השפל הגדול, משבר כלכלי עולמי, אשר הביא את רמת הפשיעה לגבהים שטרם נודעו. האיסור על מכירת משקאות חריפים (The prohibition) גרם אף הוא לאווירה כללית של פריעת החוק. היו אלו ימיהם של הגנגסטרים הגדולים מסוגו של אל קאפון, ואף של השודדים והרוצחים בדרכים מסוג ג'ון דילינג'ר, בוני טיילור וקלייד דארו.
הובר הדגיש בתחילת כהונתו את הרצון למקצוענות ולכשירות של עובדיו. הוא פיטר באופן מיידי עובדים שנראו כבלתי כשירים, ויצר סטנדרטים חדשים של קידום שלא לפי ותק אלא לפי כישורים. הוא ביקש לגייס סוכנים בעלי כישורים באכיפת החוק, ובמיוחד ביקש למצוא עורכי דין ורואי חשבון. בינואר 1928 יצר הובר תוכנית אימונים להכשרת סוכנים חדשים, וקבע מגבלת גיל לגיוס הסוכנים, בין גיל 25 לגיל 35. ה-BOI החל לפעול בשיטות מדעיות מודרניות, ונוצרה מערכת לזיהוי פושעים, ובמיוחד כרטסת ארצית של טביעות אצבעות.
הובר היה מומחה בתחום יחסי הציבור, וידע לתת באותן שנים נופך הירואי למאבקם של אנשי ה-BOI בפשיעה. למאבק בפושעים מסוימים ניתן כיסוי עיתונאי נרחב, ואדם כג'ון דילינג'ר, שנהג להתחמק ממעצר בעת שחצה את גבולות המדינות בארצות הברית, הוכרז כ"אויב הציבור מס' 1" ולאחר מכן נרדף בכל רחבי ארצות הברית, על ידי הלשכה לחקירות, שלה סמכות בכל המדינות, עד שהומת ביריות בפתח קולנוע, לאחר שמקום הימצאו הוסגר על ידי מודיע. פעולות אלו הגבירו את המוניטין של הלשכה לחקירות, ותרמו לקידומו.
הלשכה הפדרלית לחקירות - FBI.
בשנת 1935 הכריז הקונגרס של ארצות הברית על "הלשכה לחקירות" כ"לשכה הפדרלית לחקירות". היה זה לאחר שבשנת 1932 הפכה "הלשכה לחקירות" ל"לשכה לחקירות של ארצות הברית", אך שם זה היה דומה לשמה של סוכנות שעסקה באכיפת חוקי המשקאות. השם החדש Federal Beaureu of Investigations הפך לשמה של הסוכנות, ונתן לה את ראשי התיבות שבהם היא ידועה - FBI.