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

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

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

 

{{קצרמר|מתמטיקה}}