תזת צ'רץ'-טיורינג – הבדלי גרסאות

 

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

:ב. מתמטיקאים הוכיחו שקילות בין מודלים שונים של חישוב: סימון למבדא של צ'רץ' לבין מכונת טיורינג למשל וכן בין אלה לבין אוטומטים לא סופיים וכו'.

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