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

 

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