תורת הרקורסיה

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

מכונות טיורינג ופונקציות רקורסיביות

Postscript-viewer-shaded.png ערך מורחב – פונקציה רקורסיבית

בבסיס תורת הרקורסיה נמצא מושג הפונקציה הרקורסיבית - פונקציה מהטבעיים אל עצמם (פונקציה אריתמטית) שניתן לחשב באמצעות מכונות טיורינג. מכונת טיורינג בנויה מרצף של הוראות, כאשר יש רק מספר סופי של הוראות שונות (מספר זה תלוי באופן ההגדרה), ולכן עוצמת קבוצת מכונות טיורינג היא . יתר על כן, ניתן לבנות מכונת טיורינג שתקבל כקלט מספר טבעי e ותחזיר כפלט רצף של הוראות עבור מכונת טיורינג.
את המכונה שמתקבלת מהקלט e נסמן ב- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ M_e} והמספר e נקרא האינדקס של המכונה.

קיימות אינסוף שיטות שונות למנות באמצעות מכונה את כל המכונות. למעשה אי אפשר להצביע על מכונה ולומר שהיא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M_0} , כי בכל שיטת מנייה תתקבל מכונה שונה.

מספור המכונות יוצר מספור לפונקציות הרקורסיביות - את הפונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \varphi_e} מחשבים באמצעות המכונה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ M_e} כך ש-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \varphi_e (n)} הוא הפלט של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ M_e} בהינתן הקלט n. זוהי פונקציה חלקית, כלומר - יכולים להיות ערכים שעליהם הפונקציה כלל לא מוגדרת (כי המכונה לא עוצרת), ואפילו קיימות פונקציות ריקות שהמכונות שלהן לא עוצרות על שום קלט. המספור אינו חד-חד ערכי - קיימות פונקציות רקורסיביות שאינדקס שמתאים להן שונה אף שהן מחזירות ערכים זהים על כל פלט.

פונקציה רקורסיבית עם אורקל

ניתן להרחיב את מושג הרקורסיביות כך שיכלול את האפשרות לחשב מידע מתוך מידע נתון, ולא רק חישוב מאפס. לצורת החישוב הזו קוראים פונקציה רקוסיבית עם אורקל. לפונקציות אלו יש מקור מידע חיצוני בצורת פונקציה מהטבעיים לעצמם, כך שבכל שלב המכונה יכולה לשלוח "שאלה" לפונקציה- מספר טבעי, והפונקציה מחזירה את התשובה (שהיא גם כן מספר טבעי). למקור המידע החיצוני, הפונקציה, קוראים אורקל, ובמקרים רבים התשובה שתתקבל, ואפילו עצם עצירת הפונקציה על קלט מסוים תלויה באורקל- עבור אורקלים מסוימים הפונקציה תחזיר תוצאה אחת ועבור אחרים היא תחזיר תוצאה אחרת. כמו שניתן למספר את הפונקציות הרקורסיביות, כך בהינתן אורקל g, ניתן למספר את כל הפונקציות הרקורסיביות עם אותו אורקל ולכן ניתן לסמן את הפונקציה הרקורסיבית עם אורקל g ה-e ב-. אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f=\varphi^g_e} נאמר ש f ניתנת לחישוב מ-g. כל פונקציה רקורסיבית רגילה היא פונקציה רקורסיבית עם האורקל g=0.

דרגות טיורינג

באמצעות המושג של פונקציה רקורסיבית עם אורקל נוצר יחס סדר בין מאגרי המידע השונים (שמיוצגים על ידי פונקציות שלמות מהטבעיים לעצמם). את היחס הזה מסמנים ב- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \le_T} (קרי: ניתן לחישוב מ-) והוא מוגדר: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f\le_T g} אם קיים אינדקס e כך ש- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f=\varphi^g_e} . זהו יחס רפלקסיבי היות שניתן לבנות מכונה שבהינתן קלט כלשהו היא תעביר אותו אל האורקל ואת התשובה תדפיס כפלט - כלומר כל פונקציה ניתנת לחישוב מעצמה. בנוסף זהו יחס טרנזיטיבי כי אם f ניתנת לחישוב מ-g ו-g ניתנת לחישוב מ-h, כלומר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f=\varphi^g_e} ,, אז ניתן לכתוב את רצף ההוראות של המכונה ה-i בתוך המכונה ה-e כל פעם שכתוב "שאל את האורקל", וכך לקבל מכונה שמחשבת את f מ-h. יחס זה אינו אנטיסימטרי לדוגמה תמיד הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f \le_T 2f, 2f \le_T f} למרות שf ו- 2f שונים.

כדי להתגבר על הבעיה הזו מגדירים יחס שקילות שמבטא את הרעיון שבשני מאגרים יש, בסופו של דבר, את אותו מידע. זהו היחס הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv_T} שמוגדר- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f \equiv_T g} אם מתקיים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f\le_T g} וגם . מחלקות השקילות נקראות דרגות טיורינג וקבוצת כל דרגות טיורינג מסומנת ב-D. על דרגות טיורינג יחס הניתנות לחישוב (שמוגדר על ידי נציגים) הוא יחס סדר חלקי.

דרגות טיורינג כקבוצות

בכל דרגת טיורינג יש פונקציה מציינת של קבוצת מספרים טבעיים כלומר פונקציה שמקבלת רק את הערכים 0 ו-1. ניתן לראות את זה על ידי מושג הגרף של פונקציה- הקבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left\{ (x,f(x)) | x \in \N \right\}} . ניתן לזהות כל קבוצה ב- עם קבוצת מספרים טבעיים באופן רקורסיבי לדוגמה על ידי הפונקציה החד חד ערכית ועל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ (m,k) \rightarrow 2^m (2k+1)} (או כל פונקציית זיווג אחרת). בצורה הזו ניתן להמיר בצורה רקורסיבית כל פונקציה לקבוצה וכל קבוצה לפונקציה.

הרבה פעמים נוח לבנות דרגות בעלות תכונות מיוחדות באמצעות בניית קבוצה שתהיה נציגה של הדרגה ולא סתם פונקציה.

תכונות בסיסיות של דרגות טיורינג

בכל דרגה יש בדיוק הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \aleph_0} פונקציות שונות, ולכן קיימות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ 2^{\aleph_0}} דרגות טיורינג שונות. בנוסף מתחת לכל דרגה יש רק מספר בן מנייה של דרגות, כי יש רק מספר בן מנייה של פונקציות רקורסיביות מנציג כלשהו של הדרגה.

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

לכל פונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f} ניתן לבנות בעיית עצירה משלה. זוהי הקבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ K_f= \left\{ e\in \N : \varphi_e^f(e) \mbox{ halts}\right\}} .
כמו שלא ניתן לחשב את בעיית העצירה על ידי פונקציה רקורסיבית כך לכל f לא ניתן לחשב ממנה את Kf. לעומת זאת, אפשר להראות שניתן לחשב מתוך Kf את f, ולכן הדרגה של Kf גדולה ממש מהדרגה של f. אם הדרגה של f היא a מסמנים את הדרגה של Kf ב-'a (נקרא a-קפץ), זו דרגה שגדולה ממש מהדרגה של a, ולכן לא קיימת דרגה מקסימלית.

ראו גם



סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0