תזת צ'רץ'-טיורינג

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