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