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

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

# המודל של מכונת טיורינג הוא מודל פשוט, אך ניתן להראות שמודלים רבים (מכונת טיורינג עם סרטים מרובים, מכונת טיורינג לא דטרמיניסטית, ווריאציות רבות אחרות) - פעולת כולן ניתנת לביצוע על ידי מכונת טיורינג רגילה. כלומר, שינויים רבים במכונת טיורינג אינם מגדילים את יכולת החישוב שלה.

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

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