שלמות טיורינג

בתחום תורת החישוביות, מערכת של כללים לעיבוד נתונים (כגון מודל חישובי, סט הפקודות של מחשב, שפת תכנות או אוטומט תאי) נחשבת שלמה טיורינגית (Turing-complete) או אוניברסלית חישובית, אם ניתן להשתמש בה כדי לסמלץ כל מכונת טיורינג^[1][2] (מכונה שהומצאה בידי המתמטיקאי ומדען המחשב הבריטי אלן טיורינג). משמעות הדבר היא שהמערכת מסוגלת לזהות או לפרש כל מערכת אחרת של כללי עיבוד נתונים. שלמות טיורינגית משמשת דרך לתאר את העוצמה החישובית של מערכת נתונה. כמעט כל שפות התכנות המודרניות הן שלמות טיורינגית.^[4]

מושג קשור הוא שקילות טיורינג: שני מחשבים P ו-Q נקראים שקולים אם P יכול לסמלץ את Q ולהפך.^[5] השערת צ'רץ'-טיורינג גורסת שכל פונקציה שאלגוריתם מחשב מסוגל לחשב, ניתנת לחישוב בידי מכונת טיורינג. מכאן שאם מחשב כלשהו בעולם האמיתי מסוגל לסמלץ מכונת טיורינג, הוא שקול לה. מכונת טיורינג אוניברסלית יכולה לסמלץ כל מכונת טיורינג אחרת, ולכן גם את ההיבטים החישוביים הטהורים של כל מחשב אפשרי.^[6][7]

כדי להוכיח שמערכת מסוימת היא שלמה טיורינגית, די להראות שהיא יכולה לסמלץ מערכת אחרת הידועה כשלמה טיורינגית. אף מערכת פיזיקלית אינה מסוגלת להכיל זיכרון אינסופי, אולם אם מתעלמים ממגבלת הזיכרון הסופי, רוב שפות התכנות נחשבות שלמות טיורינגית.^[8][9]

שימוש לא-מתמטי

בשפה היום-יומית משתמשים לעיתים במונחים "שלם טיורינגית" ו"שקול טיורינגית" לציון שמחשב כללי או שפת תכנות כללית יכולים להדמות בקירוב להיבטים החישוביים של כל מערכת חישוב כללית אחרת. בהקשר המעשי, הדבר מתקשר למושגים כמו וירטואליזציה ואמולציה.

המחשבים הקיימים עד היום ניתנים לניתוח תפקודי כאילו היו מכונת טיורינג בעלת סרט אחד, שבה הסרט מייצג את הזיכרון – ולכן ניתן להחיל עליהם את המתמטיקה התאורטית הרלוונטית אם מפשטים מספיק את פעולתם. אולם, בשל מגבלות פיזיות, מחשבים אמיתיים הם לכל היותר שקולים לאוטומט חסום ליניארית. לעומת זאת, ההפשטה של "מחשב אוניברסלי" מוגדרת כישות שלה מערך פקודות שלם טיורינגית, זיכרון אינסופי וזמן ריצה בלתי מוגבל.

הגדרות פורמליות

בתורת החישוביות קיימים כמה מונחים קרובים המשמשים לתיאור עוצמתה החישובית של מערכת (כגון מכונה מופשטת או שפת תכנות):

שלמות טיורינגית מערכת חישובית המסוגלת לחשב כל פונקציה שמכונת טיורינג יכולה לחשב. לחלופין, מערכת המסוגלת לסמלץ מכונת טיורינג אוניברסלית.

שקילות טיורינגית מערכת שלמה-טיורינגית הנחשבת שקולה אם כל פונקציה שהיא מחשבת היא פונקציה חישיבה-טיורינגית, כלומר היא מחשבת בדיוק את מחלקת הפונקציות שמחשבות מכונות טיורינג. לחלופין, זו מערכת המסוגלת גם לסמלץ וגם להיות מסומלצת על ידי מכונת טיורינג אוניברסלית. (כל המערכות השלמות-טיורינגיות שניתנות למימוש פיזי מוכרות כיום כשקולות טיורינג – עובדה המחזקת את השערת צ'רץ'-טיורינג.

אוניברסליות (חישובית)

מערכת נקראת אוניברסלית ביחס למחלקת מערכות אם היא מסוגלת לחשב כל פונקציה שמערכות באותה מחלקה יכולות לחשב, או לסמלץ כל אחת מהן. בדרך כלל המונח "אוניברסליות" מתייחס במובלע למחלקה של מערכות שלמות טיורינגית. המונח "אוניברסלית חלשה" מציין מערכת (למשל אוטומט תאי) אשר אוניברסליותה מושגת רק לאחר שינוי בהגדרת מכונת טיורינג – למשל אם מתירים קלט המכיל אינסוף 1-ים.

היסטוריה

לשלמות טיורינגית חשיבות רבה, משום שכל תכנון מעשי של התקן חישוב ניתן לסמלוץ על ידי מכונת טיורינג אוניברסלית. השערת צ'רץ'-טיורינג קובעת שזהו חוק מתמטי – שמכונת טיורינג אוניברסלית יכולה, בעיקרון, לבצע כל חישוב שמסוגל לבצע כל מחשב מתוכנת אחר. קביעה זו אינה אומרת דבר על המאמץ הנדרש לכתיבת התוכנית, הזמן שיידרש לחישוב, או כל יכולת אחרת של המחשב שאינה נוגעת ישירות לחישוב.

צ'ארלס בבג' תכנן בשנות ה-30 של המאה ה-19 את המכונה האנליטית, אשר אילו הייתה נבנית, הייתה הופכת למכונה השלמה טיורינגית הראשונה. בבג' הבין שהמכונה מסוגלת לבצע חישובים מתקדמים ואף פעולות לוגיות פשוטות, אך לא היה מודע לכך שאין בנמצא מכונה אחרת שיכולה לעלות עליה עקרונית.

בין שנות ה-30 של המאה ה-19 לשנות ה-40 של המאה ה-20 נבנו ושוכללו מכונות חישוב מכניות כגון מחסרים וכופלים, אך אלו לא כללו ענף מותנה (conditional branch) ולכן לא היו שלמות טיורינגית.

בסוף המאה ה־19 הציע ליאופולד קרונקר הגדרות של חישוביות ופיתח את מושגי הפונקציות הרקורסיביות הפרימיטיביות. פונקציות אלה ניתנות לחישוב על ידי רצף פעולות סדור, אולם אין בהן די לבניית מחשב אוניברסלי, כי לא ניתן ליצור באמצעותן לולאה אינסופית. בראשית המאה ה־20 הוביל דויד הילברט תוכנית לאקסיומטיזציה של כל המתמטיקה, באמצעות מערכת אקסיומות וכללי היסק פורמליים לחלוטין, שניתן לבצע במכונה. עד מהרה התברר שמספר קטן של כללי היסק מספיק להפיק את כל התוצאות הנובעות מכל אוסף אקסיומות, והוכח על ידי קורט גדל בשנת 1930 שכללי היסק אלו אכן מספיקים להוכיח את כל המשפטים.

מושג החישוב עצמו הוגדר במדויק זמן קצר לאחר מכן, בעקבות משפט האי־שלמות של גדל. המשפט הראה שמערכות אקסיומות מוגבלות ביכולתן להסיק מסקנות על עצמן ועל החישוביות של אותן מסקנות. צ'רץ' וטיורינג הראו, כל אחד בנפרד, שהבעיה הדציזיונית (Entscheidungsproblem (אנ')) שהציב הילברט אינה פתירה.^[10] בכך זיהו את הליבה החישובית של משפט האי־שלמות. עבודותיהם, יחד עם תרומתו של גדל לפיתוח מושגי פונקציה רקורסיבית כללית, ביססו את ההכרה שקיימות מערכות פשוטות של הוראות שבכוחן לבצע כל חישוב. עבודת גדל הראתה שמושג החישוב הוא למעשה יחיד ועקבי.

בשנת 1941 סיים קונרד צוזה את בניית מחשב ה־Z3. צוזה לא הכיר באותה עת את עבודתו של טיורינג על חישוביות. במיוחד, ה־Z3 לא הכיל רכיב ייעודי לקפיצה מותנית, ולכן לא היה שלם טיורינגית בפועל. ואולם, בשנת 1998 הראה רוחהאס (אנ') כי ה־Z3 מסוגל, בתיאוריה, לסמלץ קפיצות מותנות, ולכן שלם טיורינגית – בתנאי שתוכנית הסרט שלו תהיה ארוכה דיה כדי לכלול את כל המסלולים האפשריים בשני ענפי כל ענף מותנה.^[11]

המחשב הראשון שהיה מסוגל לבצע קפיצה מותנית הלכה למעשה – ולכן היה שלם טיורינגית בפועל – היה ENIAC ב־1946. מחשב ה־Z4 של צוזה היה פעיל כבר ב־1945, אך התמיכה בקפיצה מותנית נוספה לו רק ב־1950.^[12]

תורת החישוביות

תורת החישוביות עוסקת בניתוח בעיות באמצעות מודל חישובי, במטרה לקבוע אם הן חישוביות ובאילו תנאים. התוצאה הידועה הראשונה בתחום זה היא כי קיימות בעיות שבהן לא ניתן לחזות מה יעשה (בזמן סופי) כל מערכת שלמה טיורינגית.

הדוגמה הקלאסית היא בעיית העצירה: בניית אלגוריתם אשר, בהינתן תוכנית בשפה שלמה טיורינגית וקלט עבור תוכנית זו, קובע אם התוכנית תסתיים לבסוף או תמשיך לנצח. אמנם קל ליצור אלגוריתם שיוכל לפתור את הבעיה עבור מקרים מסוימים, אך הוכח כי אין אפשרות לפתור אותה באופן כללי. למעשה, לכל מאפיין של הפלט הסופי של תוכנית, אי אפשר לקבוע אם יתקיים.

מגבלה זו יוצרת קשיים ממשיים בניתוח תוכניות מחשב. לדוגמה, אין אפשרות לכתוב כלי שיגן על מתכנתים מפני יצירת לולאות אינסופיות, או על משתמשים מפני קלט שעלול לגרום ללולאות כאלה.

ניתן להגבילה לבצע חישוב רק לפרק זמן מוגדר מראש (timeout), או לצמצם את העוצמה של פקודות הבקרה (למשל, לאפשר רק לולאות ש"עוברות" על איברי מערך קיים). עם זאת, משפט נוסף מראה שקיימות בעיות הניתנות לפתרון על ידי שפות שלמות טיורינגית, אך אינן ניתנות לפתרון בשום שפה המגבילה עצמה ללולאות סופיות בלבד (שפות שבהן מובטח שכל תוכנית תסתיים). לכן שפה כזו אינה שלמה טיורינגית. לדוגמה, שפה שבה מובטח שהתוכנית תמיד תסיים, לא יכולה לחשב את הפונקציה החישובית הנוצרת על ידי טיעון האלכסון של קנטור על כל הפונקציות החישוביות בשפה זו.

אורקלים של טיורינג

ערך מורחב – אורקל (מדעי המחשב)

מחשב שיש לו גישה לסרט מידע אינסופי עשוי להיות חזק יותר ממכונת טיורינג. לדוגמה, הסרט יכול להכיל את הפתרון לבעיית העצירה או לבעיה אחרת שאינה ניתנת להכרעה בידי מכונת טיורינג. סרט מידע אינסופי כזה מכונה אורקל טיורינג. גם אורקל טיורינג המכיל מידע אקראי אינו ניתן לחישוב (בהסתברות 1), שכן יש מנייה בת מנייה של חישובים אפשריים, אך מספר בלתי־מנייתי של אורקלים אפשריים. לכן מחשב עם אורקל טיורינג אקראי מסוגל לבצע חישובים שמכונת טיורינג אינה יכולה לבצע.

פיזיקה דיגיטלית

כל חוקי הפיזיקה הידועים מוליכים לתוצאות הניתנות לחישוב בקירוב על ידי מחשב דיגיטלי. היפותזת הפיזיקה הדיגיטלית גורסת שזו אינה מקריות, שכן היקום עצמו ניתן לחישוב באמצעות מכונת טיורינג אוניברסלית. משמעות הדבר היא שלא ניתן לבנות מחשב חזק יותר מבחינה חישובית ממכונת טיורינג אוניברסלית.^[13]

דוגמאות

המערכות החישוביות (אלגברות, חישובים פורמליים) שנידונות בהקשר של שלמות טיורינגית מיועדות לחקר מדעי המחשב התאורטיים. מערכות אלו נבנות באופן פשוט ככל האפשר כדי להקל על הבנת גבולות החישוב. בין הדוגמאות:

• תורת האוטומטים
• דקדוק פורמלי (יוצרי שפה)
• שפה פורמלית (מזהי שפה)
• תחשיב למדא
• מכונת פוסט-טיורינג (אנ')
• חישוב תהליכים (אנ')

רוב שפות התכנות (מודליהן המופשטים, לעיתים ללא תוספים התלויים בזיכרון סופי) – קונבנציונליות ובלתי־קונבנציונליות – הן שלמות טיורינגית. זה כולל:

• כל השפות הכלליות הנפוצות:
  • שפות תכנות פרוצדורלי כמו C ו־פסקל.
  • שפות תכנות מונחה עצמים כמו Java, Smalltalk ו־C#.
  • שפות רב־פרדיגמטיות כגון Ada, ++C, Common Lisp, Fortran, JavaScript, Object Pascal, Perl, Python, R.
• רוב השפות המבוססות על פרדיגמות נדירות יותר:
  • שפות תכנות פונקציונלי כגון Lisp ו־Haskell.
  • שפות תכנות לוגי כמו Prolog.
  • מעבדי מאקרו כלליים כמו m4.
  • שפות תכנות דקלרטיבי כמו SQL ו־XSLT.^[14][15]
  • VHDL ושפות תיאור חומרה אחרות.
  • TeX, מערכת לעימוד.
  • שפות תכנות אזוטריות (אנ') – תחום של שעשוע מתמטי, שבו מתכנתים מגלים כיצד לכתוב מבנים בסיסיים בשפה קשה במיוחד אך שקולה לטיורינג.

חלק ממערכות שכתוב (אנ') הן שלמות טיורינגית.

שלמות טיורינגית היא הצהרה מופשטת על יכולת, ולא הגדרה של תכונות שפה ספציפיות המיישמות אותה. התכונות המשמשות למימוש שלמות טיורינגית עשויות להיות שונות מאוד: בשפות פורטרן יעשה שימוש בלולאות או בפקודות goto לחזרה, בעוד ב־Haskell ו־Prolog שאין בהן לולאות ישירות, יעשה שימוש ברקורסיה. רוב שפות התכנות מתארות חישובים על ארכיטקטורת פון נוימן – הכוללת זיכרון (RAM ורשומות) ויחידת בקרה – שני רכיבים המעניקים לה שלמות טיורינגית. גם שפות פונקציונליות טהורות הן שלמות טיורינגית.^[16]

ב־SQL דקלרטיבית, שלמות טיורינגית מושגת באמצעות טבלאות משותפות רקורסיביות. כצפוי, הרחבות פרוצדורליות ל־SQL (כגון PLSQL) גם הן שלמות טיורינגית. זה ממחיש מדוע שפות חזקות אך לא שלמות טיורינגית הן נדירות: ככל שהשפה רבת עוצמה יותר מלכתחילה, כך המשימות גדלות והיעדר השלמות מורגש כחיסרון, שמעודד הרחבת השפה עד להשגת שלמות טיורינגית.

התחשיב למדא הוא שלם טיורינגית, אך רבים מהקלקולי הטיפוסיים, כולל System F, אינם כאלה. ערכן של מערכות טיפוסים בכך שהן מייצגות את רוב התוכניות השכיחות, תוך זיהוי שגיאות נוספות.

כלל 110 ומשחק החיים של קונוויי, שניהם אוטומטים תאיים, הם שלמים טיורינגית.

שלמות טיורינג לא מכוונת

חלק מהתוכנה והמשחקי מחשב הם שלמים טיורינגית באופן מקרי, כלומר – לא כתוצאה מתכנון מכוון.

תוכנה:

• Microsoft Excel^[17]

משחקים:

• Dwarf Fortress^[18]
• Cities: Skylines^[19]
• Opus Magnum
• Minecraft^[20]
• Magic: The Gathering^[21][22]
• משחק שולה המקושים על רשת אינסופית^[23]

רשתות חברתיות:

• Habbo Hotel

שפות חישוביות:

• תבניות C++ (C++ templates)^[24]
• מחרוזות הפורמט של printf^[25]
• מערכת הטיפוסים של TypeScript^[26]
• פקודת MOV בשפת x86 Assembly^[27]

ביולוגיה:

• מחשוב כימי – רשתות תגובה כימיות^[28][29] ומחשבים מבוססי DNA.^[30]

ראו גם

• היררכיית חומסקי
• משפט רייס

קישורים חיצוניים

• שלמות טיורינג, באתר MathWorld (באנגלית)