תזה של Church-Turing מתייחסת למושג של שיטה יעילה, שיטתית או מכנית בלוגיקה, מתמטיקה ומדעי המחשב. הוא מנוסח כתיאור של המושג האינטואיטיבי של יכולת חישוב, וביחס לפונקציות רקורסיביות כלליות, מכונה לעתים קרובות יותר התזה של Church. זה מתייחס גם לתיאוריה של פונקציות הניתנות לחישוב מחשב. התזה הופיעה בשנות ה-30, כאשר המחשבים עצמם עדיין לא היו קיימים. מאוחר יותר הוא נקרא על שם המתמטיקאי האמריקאי אלונסו צ'רץ' ועמיתו הבריטי אלן טיורינג.
יעילות השיטה להשגת התוצאה
המכשיר הראשון שדמה למחשב מודרני היה ה-Bombie, מכונה שנוצרה על ידי המתמטיקאי האנגלי אלן טיורינג. הוא שימש לפענוח הודעות גרמניות במהלך מלחמת העולם השנייה. אך לצורך התזה והפורמליזציה שלו של מושג האלגוריתם, הוא השתמש במכונות מופשטות, שנקראו מאוחר יותר מכונות טיורינג. תזה מציגהעניין עבור מתמטיקאים ומתכנתים כאחד, מכיוון שהרעיון הזה היווה השראה ליוצרי המחשבים הראשונים.
בתוראת יכולת החישוב, התזה של Church-Turing ידועה גם בתור ההשערה לגבי טבען של פונקציות הניתנות לחישוב. הוא קובע כי עבור כל פונקציה הניתנת לחישוב אלגוריתמית על מספרים טבעיים, קיימת מכונת טיורינג המסוגלת לחשב אותה. או, במילים אחרות, יש אלגוריתם שמתאים לזה. דוגמה ידועה ליעילותה של שיטה זו היא מבחן טבלת האמת לבדיקת טאוטולוגיה.
דרך להשיג כל תוצאה רצויה נקראת "יעיל", "שיטתית" או "מכנית" אם:
- השיטה מצוינת במונחים של מספר סופי של הוראות מדויקות, כל הוראה מבוטאת באמצעות מספר סופי של תווים.
- זה יפעל ללא שגיאות, יפיק את התוצאה הרצויה במספר מסוים של שלבים.
- השיטה יכולה להתבצע על ידי אדם ללא סיוע בכל ציוד מלבד נייר ועיפרון
- זה לא דורש הבנה, אינטואיציה או כושר המצאה מצד האדם שמבצע את הפעולה
קודם לכן במתמטיקה, נעשה שימוש במונח הבלתי פורמלי "ניתן לחישוב יעיל" כדי להתייחס לפונקציות שניתן לחישוב באמצעות עיפרון ונייר. אבל עצם הרעיון של יכולת חישוב אלגוריתמית היה אינטואיטיבי יותר מכל דבר קונקרטי. כעת היא אופיינה בפונקציה עם ארגומנט טבעי, שעבורה קיים אלגוריתם חישוב. אחד ההישגים של אלן טיורינג היהייצוג של פרדיקט מדויק פורמלית, שבעזרתו ניתן יהיה להחליף את הבלתי פורמלי, אם נעשה שימוש בתנאי יעילות השיטה. צ'רץ' גילתה את אותה תגלית.
מושגים בסיסיים של פונקציות רקורסיביות
שינוי הפרדיקטים של טיורינג, במבט ראשון, נראה שונה מזה שהציע עמיתו. אך כתוצאה מכך התברר שהם שוות ערך, במובן זה שכל אחד מהם בוחר את אותה קבוצה של פונקציות מתמטיות. התזה של Church-Turing היא הקביעה שמערך זה מכיל כל פונקציה שניתן להשיג את ערכיה בשיטה העומדת בתנאי היעילות. היה הבדל נוסף בין שתי התגליות. זה היה שצ'רץ' שקל רק דוגמאות של מספרים שלמים חיוביים, בעוד טיורינג תיאר את עבודתו כמכסה פונקציות ניתנות לחישוב עם משתנה אינטגרלי או ממשי.
פונקציות רקורסיביות נפוצות
הניסוח המקורי של Church קובע שניתן לבצע את החישוב באמצעות חשבון λ. זה שווה ערך לשימוש בפונקציות רקורסיביות גנריות. התזה של Church-Turing מכסה יותר סוגי חישוב ממה שחשבו במקור. למשל, קשור לאוטומטים סלולריים, קומבינטורים, מכונות רישום ומערכות החלפה. בשנת 1933, המתמטיקאים קורט גדל וז'אק הרברנד יצרו הגדרה פורמלית של מחלקה הנקראת פונקציות רקורסיביות כלליות. הוא משתמש בפונקציות שבהן יותר מארגומנט אחד אפשרי.
יצירת שיטהλ-calculus
בשנת 1936 יצרה כנסיית אלונסו שיטת קביעה שנקראת λ-calculus. הוא היה קשור למספרים טבעיים. בתוך λ-calculus, המדען קבע את הקידוד שלהם. כתוצאה מכך, הם נקראים מספרי כנסייה. פונקציה המבוססת על מספרים טבעיים נקראה λ-למחשב. הייתה הגדרה אחרת. הפונקציה מהתזה של צ'רץ' נקראת λ-מחשב בשתי תנאים. הראשון נשמע כך: אם הוא היה מחושב על יסודות הכנסייה, והתנאי השני היה האפשרות להיות מיוצג על ידי חבר ב-λ-calculus.
גם בשנת 1936, לפני שלמד את עבודתו של עמיתו, טיורינג יצר מודל תיאורטי למכונות המופשטות הקרויות כעת על שמו. הם יכלו לבצע חישובים על ידי מניפולציה של הדמויות בקלטת. זה חל גם על פעילויות מתמטיות אחרות שנמצאות במדעי המחשב התיאורטיים, כגון מחשוב הסתברותי קוונטי. הפונקציה מהתזה של צ'רץ' הוכחה רק מאוחר יותר באמצעות מכונת טיורינג. בתחילה, הם הסתמכו על λ-calculus.
יכולת חישוב פונקציונלית
כאשר מספרים טבעיים מקודדים כראוי כרצפי תווים, אומרים שפונקציה במספרים טבעיים ניתנת לחישוב טיורינג אם המכונה המופשטת מצאה את האלגוריתם הנדרש והדפיסה את הפונקציה הזו בקלטת. מכשיר כזה, שלא היה קיים בשנות ה-30, ייחשב בעתיד למחשב. מכונת טיורינג המופשטת והתזה של צ'רץ' בישרו עידן של התפתחותהתקני מחשוב. הוכח שמעמדות הפונקציות שהוגדרו רשמית על ידי שני המדענים חופפים. לכן, כתוצאה מכך, שולבו שתי ההצהרות לאחת. גם לפונקציות חישוביות ולתזה של צ'רץ' הייתה השפעה חזקה על מושג יכולת החישוב. הם גם הפכו לכלי חשוב ללוגיקה מתמטית ולתורת ההוכחה.
הצדקה ובעיות השיטה
יש דעות סותרות על התזה. עדויות רבות נאספו ל"השערת העבודה" שהציעו צ'רץ' וטיורינג ב-1936. אבל כל השיטות או הפעולות הידועות לגילוי פונקציות חדשות הניתנות לחישוב יעיל מאלו נתונות היו קשורות לשיטות לבניית מכונות, שלא היו קיימות אז. כדי להוכיח את התזה של Church-Turing, מתחילים מהעובדה שכל מודל חישוב ריאליסטי שווה ערך.
בשל מגוון הניתוחים השונים, זה נחשב בדרך כלל לראיה חזקה במיוחד. כל הניסיונות להגדיר בצורה מדויקת יותר את הרעיון האינטואיטיבי של פונקציה הניתנת לחישוב יעיל התברר כשווה ערך. כל ניתוח שהוצע הוכיח שהוא מייחד את אותה מחלקה של פונקציות, כלומר אלו שניתנות לחישוב על ידי מכונות טיורינג. אבל כמה מודלים חישוביים התבררו כיעילים יותר מבחינת זמן ושימוש בזיכרון עבור משימות שונות. מאוחר יותר צוין שהמושגים הבסיסיים של פונקציות רקורסיביות והתזה של צ'רץ' הם היפותטיים למדי.
תזה M
חשוב להבחין בין התזה של טיורינג לבין הקביעה שכל דבר שניתן לחשב על ידי מכשיר מחשוב יכול להיות מחושב על ידי המכונה שלו. לאפשרות השנייה יש הגדרה משלה. גנדי קורא למשפט השני "תזה M". זה הולך ככה: "כל מה שניתן לחשב על ידי מכשיר ניתן לחשב על ידי מכונת טיורינג." במובן הצר של התזה, מדובר בהצעה אמפירית שערך האמת שלה אינו ידוע. התזה של טיורינג ו"תזה M" לפעמים מבולבלים. הגרסה השנייה שגויה בגדול. תוארו מכונות מותנות שונות שיכולות לחשב פונקציות שאינן ניתנות לחישוב של טיורינג. חשוב לציין שהתזה הראשונה אינה כרוכה בשנייה, אלא תואמת את השקר שלה.
השלכה הפוכה של התזה
בתוראת יכולת החישוב, התזה של צ'רץ' משמשת כתיאור של רעיון יכולת החישוב על ידי מחלקה של פונקציות רקורסיביות כלליות. סטיבן קליין האמריקאי נתן ניסוח כללי יותר. הוא קרא רקורסיבי חלקית לכל הפונקציות החלקיות הניתנות לחישוב על ידי אלגוריתמים.
השלכה הפוכה מכונה בדרך כלל התזה ההפוכה של הכנסייה. זה טמון בעובדה שכל פונקציה רקורסיבית של מספרים שלמים חיוביים מוערכת ביעילות. במובן הצר, תזה פשוט מציינת אפשרות כזו. ובמובן רחב יותר, הוא מופשט מהשאלה האם המכונה המותנית הזו יכולה להתקיים בו.
מחשבי קוונטים
המושגים של פונקציות ניתנות לחישוב והתזה של צ'רץ' הפכו לתגלית חשובה עבור מתמטיקה, תורת המכונות ומדעים רבים אחרים. אבל הטכנולוגיה השתנתה מאוד וממשיכה להשתפר. ההנחה היא שמחשבים קוונטיים יכולים לבצע משימות נפוצות רבות בפחות זמן מאשר מודרניים. אבל נותרו שאלות, כמו בעיית העצירה. מחשב קוונטי לא יכול לענות על זה. ולפי התזה של Church-Turing, אין גם מכשיר מחשוב אחר.
