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