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