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

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