תזת צ'רץ'-טיורינג

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

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

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

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

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

  1. המודל של מכונת טיורינג הוא מודל פשוט, אך ניתן להראות שמודלים רבים (מכונת טיורינג עם סרטים מרובים, מכונת טיורינג לא דטרמיניסטית, ווריאציות רבות אחרות) - פעולת כולן ניתנת לביצוע על ידי מכונת טיורינג רגילה. כלומר, שינויים רבים במכונת טיורינג אינם מגדילים את יכולת החישוב שלה.
  2. מתמטיקאים הוכיחו שקילות בין מודלים שונים של חישוב: תחשיב למדא של צ'רץ' לבין מכונת טיורינג למשל וכן בין אלה לבין אוטומטים לא סופיים וכדומה.
  3. הוכח שניתן לחשב על ידי מכונות טיורינג כל דבר שניתן לחישוב על ידי תוכנה שמשתמשת ביכולות הבסיסיות של אסמבלר (שפת סף ששפות התכנות המודרניות מתורגמות אל אחד מהסוגים שלה) ושל שפות התכנות המודרניות. לדוגמה: מכונת טיורינג יכולה לגשת לתאים בזיכרון לפי מספר ששמור במקום מסוים בזיכרון (הדומה לשימוש במצביעים בשפות התכנות). לבצע חישובים בסיסיים, לקבוע את הפעולה או רצף הפעולות שיבוצעו ע"פ תנאי (מה ששקול לפקודת קפיצה וקפיצה מותנית באסמבלי וללולאות ומשפטי if בשפות תכנות עיליות), וכן לעצור את פעולתה ולקרוא למכונת טיורינג אחרת שתפעל במקומה (באופן דומה, גם תוכנה בשפת C ושפות אחרות יכולה לקרוא לפונקציית עזר ובפרט הן יכולות לקרוא לעצמן עם קלט אחר או אפילו אותו קלט, מה ששקול ללולאה אינסופית.
P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.