פונקציה פרימיטיבית רקורסיבית – הבדלי גרסאות

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


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


==הגדרה==
==הגדרה==

גרסה מ־13:52, 30 במאי 2008

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

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

הגדרה

בתורת החישוביות, מחלקה של פונקציות שלמות, נקראת סגורה תחת רקורסיה פרימיטיבית (Primitive Recursively Closed או PRC), אם היא סגורה תחת הפעולה של יצירת פונקציה חדשה מהפונקציות קיימות באופן הבא:

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

היא פונקציה הנוצרת מהן על ידי רקורסיה פרימיטיבית.

מחלקת הפונקציות הרקורסיביות פרימיטיביות היא מחלקת הפונקציות שמכילה את הפונקציות התחיליות:

  • - פונקציית העוקב.
  • - פונקציית האפס.
  • - פונקציית ההטלה לרכיב ה-i.

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

דוגמאות

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

להלן מספר פונקציות פרימיטיביות רקורסיביות פשוטות:

חיבור

פונקציית החיבור:
היא פונקציה פרימיטיבית רקורסיבית:

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

כפל, חזקה, ועצרת

פונקציית הכפל, החזקה והעצרת:




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

חיסור

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

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

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

מכאן ניתן להגדיר את החיסור:

חילוק

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

נגדיר את פונקציית החילוק:

- כאשר החיסור פועל כמו שהוגדר לעיל.

שימושים

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

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

קשר למודלים חישוביים שונים

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

למרות שנובע מכך שפונקציות רקורסיביות רבות ביותר הן פרימיטיביות רקורסיביות, קיימות פונקציות רקורסיביות שאינן פרימיטיביות רקורסיביות, כגון פונקציית אקרמן.