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