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

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

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