נאמר ש-formula_62מתחלק ב-formula_49אם ורק אם formula_72. באמצעות חילוק בשארית קל להיווכח בטענה חשובה: המספר formula_73 הוא שורש של הפולינום formula_74 אם ורק אם הביטוי formula_75 מחלק את formula_13.
לעיתים ניתן לקבוע אם פולינום שמקדמיו שלמים ניתן לפירוק כמכפלת שני פולינומים בעזרת קריטריון איזנשטיין.
שדה הפונקציות הרציונליות.
שדה השברים הנוצר מהחוג formula_46 הוא קבוצת כל הפונקציות הרציונליות, המסומנת ב formula_78. אלו כל הביטויים מהצורה formula_79, כאשר formula_80.
פולינומים במספר משתנים.
ניתן להכליל את מושג הפולינום לפולינמים במספר משתנים. פולינום ב-2 משתנים formula_81, לדוגמה, הוא ביטוי מהצורה formula_82. בצורה דומה ניתן להגדיר פולינום ב-formula_34 משתנים.
קבוצת כל הפולינומים ב-formula_34 משתנים מעל חוג היא עדיין חוג, אך עבור formula_85 זהו אינו חוג ראשי. חוג הפולינומים באינסוף משתנים אינו חוג נותרי.
תת-קבוצה חשובה של פולינומים במספר משתנים הם הפולינומים הסימטריים. פולינום formula_86 ב-formula_34 משתנים formula_88 נקרא סימטרי אם לכל תמורה formula_89 מתקיים
כל פולינום סימטרי ניתן להצגה כפולינום ב-formula_91 כאשר formula_91 הם הפולינומים הסימטריים האלמנטריים ב-formula_34 משתנים. לדוגמה, עבור formula_94 הפולינומים הסימטריים האלמנטריים הם:
שכבת השיחה של מודל ה-OSI
שכבת השיחה (session) אחראית על יצירת, ניהול, וסגירת שיחות בין התוכניות הפועלות בשני קצוות (nodes) של רשת מחשבים. היא משמשת את שכבת הייצוג ומשתמשת בשכבת התעבורה על מנת להעביר נתונים על גבי הרשת והיא השכבה החמישית במודל ה-OSI.
השיחות הללו, שעל שמן נקראת השכבה הם כל התקשרות בין שני מחשבים, נוצרת על ידי אחת משתי השכבות העליונות של מודל ה-OSI. לדוגמה, כאשר משתמש מבקש דף אינטרנט - נפתח תהליך, השרת מחזיר את דף האינטרנט המבוקש - והתהליך נסגר. שכבת השיחה מחלקת את השיחות לשני סוגים:
פרוטוקולים של שכבת השיחה.
ASP, PPTP, SSH, NFS, RPC, SSL
מכונת טיורינג
מכונת טיורינג (באנגלית: Turing machine) היא מודל חישובי מתמטי אשר באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).
מכונת טיורינג מתארת בצורה פורמלית-מתמטית, כיצד ניתן לבצע פעולות חישוביות שונות כגון זיהוי מילים השייכות לשפה פורמלית, ביצוע פעולות חיפוש ומיון בקלט ועוד, והיא למעשה האוטומט החזק ביותר לביצוע חישובים, ולמעשה לעיתים המושג "חישוב" מוגדר על סמך פעולות הניתנות לביצוע באמצעות מכונת טיורינג.
מכונת טיורינג מתוארת באופן דמיוני כסרט אינסופי של תאים וראש קריאה בעל זיכרון סופי היכול לקרוא את תוכנו של התא שמעליו הוא ממוקם, לכתוב באותו התא וכן לנוע ימינה או שמאלה על הסרט. המכונה מקבלת את הקלט שלה באמצעות הסרט, עליו היא יכולה גם לכתוב, ולזוז כרצונה לכל נקודה על גביו.
כאמור למרות שהמודל נראה פשטני ודל, התזה של צ'רץ'-טיורינג קובעת שכל חישוב או אלגוריתם בר-ביצוע, ניתן לתרגם למכונת טיורינג. מבחינה זו, מכונת טיורינג שקולה לכל מחשב, ולכן משמשת במדעי המחשב, בעיקר בתורת הסיבוכיות ובתורת החישוביות, כבסיס לחקר יכולותיו ומגבלותיו התאורטיות של המחשב.
את המודל הציע אלן טיורינג בשנת 1936, טרם המצאת המחשב המודרני, כדי ליצור הגדרה מתמטית מדויקת של אלגוריתם, או "תהליך מכני" חישובי.
שלמות טיורינג מוגדרת כיכולת הרצת אלגוריתמים הדומה למכונת טיורינג אוניברסלית (למעט הזיכרון הסופי של התקן החישוב בו הוא שונה ממכונת טיורינג).
רקע.
אלן טיורינג פיתח את מכונת טיורינג כניסוי מחשבתי, בניסיון לזהות שאלות מתמטיות, שאינן ניתנות להכרעה ובכך להבדילן משאלות מתמטיות הניתנות להכרעה, שלגביהן משפט אי השלמות של גדל אינו תקף.
למעשה מכונות טיורינג מזהות האם קלט עונה על תבנית מוגדרת מסוימת, או באופן פורמלי יותר, האם מילה שהוזנה למכונה כקלט היא מילה בשפה פורמלית מסוימת. באמצעות המודל החישובי ניתן לראות כי ישנן שפות אשר עבורן ניתן לתאר מכונת טיורינג אשר תמיד תכריע האם מילה נמצאת בשפה או האם היא אינה נמצאת בשפה. שפות אלו מכונות שפות "כריעות". בנוסף, קיימות שפות אשר אינן כריעות אך כן קיימות מכונות טיורינג אשר מזהות כל מילה ששייכת להן, אולם ייתכן שהן לעולם לא יעצרו אם המילה אינה שייכת לשפה. שפות אלו מכונות "ניתנות לזיהוי". ניתן להוכיח כי קיימות שפות, או במילים אחרות קיימות בעיות, אשר אינן ניתנות לחישוב במכונת טיורינג, ולכן לא ניתנות לחישוב באמצעות כל מחשב.
תיאור המרכיבים.
מכונת טיורינג מורכבת מהרכיבים הבאים:
כל מרכיביה של מכונת טיורינג הם סופיים, מלבד הסרט שאינו מוגבל באורכו.
תיאור אופן הפעולה.
מכונת טיורינג מתחילה את פעולתה במצב ההתחלתי, כשעל הסרט כתוב מידע כלשהו - הקלט. הקלט הוא תמיד סופי, והאלפבית של האותיות שמרכיבות אותו הוא חלקי ממש לאלפבית של הסימנים שניתן לרשום על הסרט. בפרט הסמל "ריק" לא נחשב לחלק מאלפבית הקלט, כדי שיהיה ברור היכן הקלט נגמר. המכונה יכולה לשנות את מצבו של הסרט ולבסוף עשויה לעצור. נהוג להסתכל על החלק של הסרט שבין תחילת הסרט והמקום שבו הראש נעצר בתור הפלט של המכונה.
בצורת חשיבה זו, ניתן לראות את מכונת טיורינג כפונקציה שהופכת קלט לפלט. המכונה לא בהכרח מסיימת את ריצתה עבור כל קלט, ולכן יכולים להיות ערכים שעבורם הפונקציה לא מוגדרת.
מכונת טיורינג ספציפית, בהתאם לתיאור המופיע לעיל, היא מעין מחשב שנועד לבצע תוכנית מסוימת (כלומר, לחשב פונקציה מסוימת). טיורינג הראה שניתן לבנות מכונה המכוּנה מכונת טיורינג אוניברסלית שמקבלת כקלט תיאור של טבלת הפעולה של מכונת טיורינג ספציפית ואחר כך את הקלט לאותה מכונת טיורינג, כך שמכונת טיורינג אוניברסלית תקרא את טבלת הפעולה, לאחר מכן תקרא את הקלט, ואז תרשום על הסרט את תוצאות פעולתה של מכונת הטיורינג שקיבלה כקלט על הקלט הנתון לאותה מכונה. בצורה זו ניתן באמצעות מכונה אחת לדמות את פעולתן של כל מכונות הטיורינג (בדומה למחשב רגיל, שאינו מיועד לביצוע פעולה ספציפית, אלא מקבל כקלט גם את התוכנה שעליו להריץ).
אחד מסוגי השאלות שניתן להציב בפני מכונת טיורינג הוא שאלות אודות אופן פעולתן של מכונות טיורינג אחרות. רבות משאלות אלה אינן ניתנות להכרעה. דוגמה לשאלה כזאת שבה עסק טיורינג, היא השאלה האם מכונת טיורינג נתונה תגיע לעצירה כאשר היא פועלת על קלט נתון או על קלט כלשהו. בעיה זו ידועה בשם בעיית העצירה, וטיורינג הראה שהיא אינה ניתנת להכרעה.
מכונת טיורינג היא מודל מופשט לחלוטין, והמסקנות הנובעות ממנו אינן דורשות מימוש פיזי של המודל. יחד עם זאת ברור שניתן לממש את מכונת טיורינג על כל מחשב מודרני (מלבד אינסופיות הסרט, שאינה מתיישבת עם סופיות הזיכרון של מחשב ממשי). עם זאת, ניתן לתכנת ישירות במודל מכונת טיורינג, לדוגמה בשפת התכנות BF.
מכונות טיורינג חלופיות.
בנוסף למודל הבסיסי, הוגדרו במשך השנים מספר מודלים חלופיים למכונת טיורינג המכלילים או מגבילים את ההגדרה המקורית, כדי להביע סוגים אחרים של חישוב. מודלים אלו מהווים כלי חשוב במדעי המחשב בכלל ובתורת הסיבוכיות בפרט, ובין השאלות החשובות במדעי המחשב היא הבנה מלאה של הקשרים בין מודלים כאלו. המודלים החלופיים המרכזיים הם אלו:
שימושים של מכונות טיורינג.
מכונות טיורינג משמשות במדעי המחשב, ובפרט בחישוביות ובתורת הסיבוכיות - להוכחות שונות. דוגמאות חשובות הן:
מבחן טיורינג
מבחן טיורינג הוא כינוי למבחן שהציע אלן טיורינג בשנת 1950, במאמר שפרסם בכתב העת Mind, כמדד אפשרי למידה שבה יש למכונה כלשהי אינטליגנציה. במקור טיורינג כינה מבחן זה "משחק החיקוי". המבחן נעשה בדרך הבאה: חוקר מקיים דיאלוג בשפה טבעית עם שני גורמים סמויים מעיניו, האחד אדם והשני מכונה. אם החוקר אינו מסוגל לקבוע בביטחון מי האדם ומי המכונה, אזי המכונה עברה בהצלחה את המבחן. כדי לפשט את המבחן, הוא נערך בערוץ תקשורת טקסטואלי בלבד.
מטרת הניסוי הוא לבדוק את הבינה המלאכותית והאם הגיעה לרמה של מוח אנושי. טיורינג הציע מבחן זה כתחליף לשאלה הטעונה רגשית, "האם מכונות מסוגלות לחשוב?" (שאלה שאליה התייחס מאוחר יותר מדען המחשב אדסחר דייקסטרה, ואמר "השאלה האם מחשב יודע לחשוב דומה לשאלה האם צוללת יודעת לשחות", וגם טיורינג עצמו ציין שהיא "כה חסרת משמעות שאין טעם לדון בה").
קשה לצפות מתי תהיה מכונה שתעבור את "מבחן טיורינג", אך בגרסה מוגבלת של מבחן זה, שבה השאלות מוגבלות לתחום צר מסוים, ניתן להצביע כבר היום על תחומים שבהם יכולתו של המחשב אינה נופלת מזו של האדם (אם כי ניתן לטעון שגם מצב זה אינו מהווה הצלחה במבחן טיורינג). דוגמה לתחום כזה היא משחק השחמט, שבו תוכנת השחמט כחול עמוק של IBM ניצחה את גארי קספרוב בשנת 1996, גדול השחמטאים אז. דוגמה עם תחום מעט יותר רחב היא הצלחתו של המחשב ווטסון (Watson) בשעשועון הטריוויה ג'פרדי! (!Jeopardy) (הגרסה המקורית האמריקאית ל"מלך הטריוויה" ששודרה בישראל).