הועלה לאתר:  
מספר עמודים: 32
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת החישוביות - חלק ראשון

סיכום מאת: ניר אדר

2.3. מודל ה-RAM

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

  1. זיכרון אינסופי (בן מניה) הממוען על ידי הכתובות plot:\[0, \pm 1, \pm 2,...\]. כל תא יכול להכיל כל מספר שלם ביצוג בינארי.
  2. מספר סופי של רגיסטרים plot:\[{r_1},{r_2},...,{r_n}\]. כל רגיסטר יכול להכיל כל מספר שלם ביצוג בינארי.

    מוגדרים שלושה רגיסטרים מיוחדים:

    plot:\[{r_1}\] - משמש כ-PC (Program Counter).

    plot:\[{r_2}\] - רגיסטר הקלט.

    plot:\[{r_3}\] - רגיסטר הפלט.
  3. סט הפקודות: סט הפקודות במודל מכיל מספר סופי של פקודות "אסמבלר" רגילות. דוגמא (!) לסט פקודות אפשרי:
  • plot:\[add\left( {{r_i},{r_j}} \right)\] - plot:\[{r_i} = {r_i} + {r_j}\].
  • plot:\[{\text{load}}\,\,{r_i} \leftarrow \left( {{r_j}} \right) + \] - הכנס ל-plot:\[{r_i}\] את תוכן התא המוצבע על ידי plot:\[{r_j}\] ואחר כך הוסף אחד לרגיסטר plot:\[{r_j}\].
  • plot:\[{\text{store }}{r_i} \to \left( {{r_j}} \right)\] - כתוב את תוכן plot:\[{r_i}\] בתא המוצבע על ידי plot:\[{r_j}\].
  • plot:\[{\text{inc }}{r_i}\] - הגדל את plot:\[{r_i}\] ב-1.
  • plot:\[{\text{dec }}{r_i}\] - הקטן את plot:\[{r_i}\] ב-1.
  • plot:\[{\text{bgt }}{r_i}?{r_j}\] - אם plot:\[{r_i}\] גדול מאפס, אזי plot:\[{\text{PC}} \leftarrow {r_j}\].
  • plot:\[{\text{halt}}\] - עצירת החישוב.
  1. צעד חישוב:

א.      קרא את המספר שבכתובת המוצבעת על ידי ה-PC.

ב.      plot:\[{\text{PC}} \leftarrow {\text{PC}} + 1\].

ג.       פענח את הפקודה שנקראה ובצע אותה.

ד.      חזור ל-א'.



  1. מהלך החישוב:

א.      מצב התחלתי:

- קוד התוכנית שתבוצע נמצא בזיכרון החל מכתובת 0. תוכן תאי הזיכרון האחרים הינו 0.

- plot:\[{r_2}\] מכיל את הקלט וכל שאר הרגיסטרים מאותחלים בערך 0.

ב.      ביצוע צעדי חישוב עד שמתבצעת פקודת halt.

ג.       אם המכונה עוצרת הפלט הינו התוכן של plot:\[{r_3}\] ברגע העצירה.

מעט כיוון על ההוכחה שמודל ה-RAM שקול למכונת טיורינג.

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

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



תגיות המסמך:

לפרק הקודם2.2.1. תרגיל
לפרק הבא3. מכונה אוניברסלית
מאת: דנה

החלק הראשון

בבקשה
מאת: אני

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299
מאת: רועי

אני חייב את המסמך הזה...הצילו

מאת: חשוון

מתי המסמך יחזור?
שיתוף:
| עוד