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