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