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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

בתחום תורת החישוביות, מערכת של כללים לעיבוד נתונים (כגון מודל חישובי, סט הפקודות של מחשב, שפת תכנות או אוטומט תאי) נחשבת שלמה טיורינגית (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]

דוגמאות

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

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

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

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

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

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

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

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

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

תוכנה:

משחקים:

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

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

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

ביולוגיה:

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

ראו גם

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

הערות שוליים

  1. ↑ Tom Stuart (2013). Understanding Computation: From Simple Machines to Impossible Programs. O'Reilly Media. p. 209. ISBN 978-1-4493-3011-8.
  2. ↑ Cristian S Calude (2024). To Halt Or Not To Halt? That Is The Question. World Scientific. p. 30. ISBN 978-981-12-3229-9.
  3. ↑ Michaelson, Greg (14 בפברואר 2020). "Programming Paradigms, Turing Completeness and Computational Thinking". The Art, Science, and Engineering of Programming. 4 (3). doi:10.22152/programming-journal.org/2020/4/4. {{cite journal}}: (עזרה)
  4. ↑ יש הסוברים שחישוב שלם-טיורינג הוא הפרדיגמה התאורטית היחידה שעליה מושתת מדעי המחשב כיום, ושגישה זו חולשת הן על השפות והן על שיטות החשיבה החישוביות.[3]
  5. ↑ Göktürk Üçoluk; Sinan Kalkan (2012). Introduction to Programming Concepts with Case Studies in Python. Springer Science & Business Media. p. 13. ISBN 978-3-7091-1343-1.
  6. ↑ Ben Goertzel (2013). The Structure of Intelligence: A New Mathematical Model of Mind. Springer. p. 13. ISBN 978-1-4612-4336-6.
  7. ↑ Alan Garnham (2017). Artificial Intelligence: An Introduction. Routledge. p. 164. ISBN 978-1-351-33786-1.
  8. ↑ Torben Ægidius Mogensen (2022). Programming Language Design and Implementation. Springer Nature. p. 6. ISBN 978-3-031-11806-7.
  9. ↑ John R. Woodward (2003). "Modularity in Genetic Programming". Genetic Programming: 6th European Conference, EuroGP 2003. Springer. p. 258. doi:10.1007/3-540-36599-0_23. ISBN 978-3-540-00971-9.
  10. ↑ Hodges, Andrew (1992), Alan Turing: The Enigma, London: Burnett Books, p. 111, ISBN 0-04-510060-8
  11. ↑ Rojas, Raul (1998). "How to make Zuse's Z3 a universal computer". Annals of the History of Computing. 20 (3): 51–54. doi:10.1109/85.707574.
  12. ↑ Rojas, Raúl (2014-02-01). "Konrad Zuse und der bedingte Sprung". Informatik-Spektrum (בגרמנית). 37 (1): 50–53. doi:10.1007/s00287-013-0717-9.
  13. ↑ Schmidhuber, Jürgen (1997), "A computer scientist's view of life, the universe, and everything", Foundations of Computer Science: Potential – Theory – Cognition, Lecture Notes in Computer Science, Springer, vol. 1337, pp. 201–208, doi:10.1007/bfb0052088
  14. ↑ "Cyclic Tag System". PostgreSQL wiki. 8 באוגוסט 2011. {{cite web}}: (עזרה)
  15. ↑ "Universal Turing Machine in XSLT". Unidex. 30 במרץ 2001. {{cite web}}: (עזרה)
  16. ↑ Rauber, Thomas; Rünger, Gudula (2013). Parallel programming: for multicore and cluster systems. Springer. ISBN 9783642378010.
  17. ↑ "Announcing LAMBDA: Turn Excel formulas into custom functions". TECHCOMMUNITY.MICROSOFT.COM (באנגלית). נבדק ב-2025-06-29.
  18. ↑ Andrew Cedotal, Dwarf Fortress Computer - Turing Machine, The Mary Sue, ‏2010-04-16 (באנגלית)
  19. ↑ Cities: Skylines Map Becomes A Poop-Powered Computer, Kotaku, ‏2019-07-17 (באנגלית)
  20. ↑ Staff Writer, PCWorld, This 8-bit processor built in Minecraft can run its own games, PCWorld (באנגלית)
  21. ↑ Churchill, Alex; Biderman, Stella; Herrick, Austin (2020). Magic: The Gathering Is Turing Complete (PDF). 10th International Conference on Fun with Algorithms.
  22. ↑ Jennifer Ouellette, It’s possible to build a Turing machine within Magic: The Gathering, Ars Technica, ‏2019-06-23 (באנגלית)
  23. ↑ Wayback Machine, web.mat.bham.ac.uk
  24. ↑ Meyers, Scott (2005). Effective C++: 55 specific ways to improve your programs and designs (מהדורה שלישית ed.). Addison-Wesley. ISBN 0321334876.
  25. ↑ Carlini, Nicolas; Barresi, Antonio; Payer, Mathias; Wagner, David; Gross, Thomas R. (אוגוסט 2015). "Control-flow bending: on the effectiveness of control-flow integrity". Proceedings of the 24th USENIX Security Symposium. pp. 161–176.
  26. ↑ Ryan Dabler, TypeScript and Turing Completeness, Medium, ‏2021-09-23 (באנגלית)
  27. ↑ Wayback Machine, stedolan.net
  28. ↑ Chen, Yuan-Jyue; Dalchau, Neil; Srinivas, Niranjan; Phillips, Andrew; Cardelli, Luca; Soloveichik, David; Seelig, Georg (אוקטובר 2013). "Programmable chemical controllers made from DNA". Nature Nanotechnology. 8 (10): 755–762. doi:10.1038/nnano.2013.189.
  29. ↑ Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik; Soloveichik, David. "Enzyme-free nucleic acid dynamical systems". Science. 358 (6369): eaal2052. doi:10.1126/science.aal2052.
  30. ↑ Shapiro, Ehud. "A Mechanical Turing Machine: Blueprint for a Biomolecular Computer". Interface Focus בדצמבר 1999. 2 (4): 497–503. doi:10.1098/rsfs.2011.0118.
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

אוחזר מתוך "https://he.hamichlol.org.il/w/index.php?title=שלמות_טיורינג&oldid=3373974"