» נושאי לימוד
» נושאי לימוד
יום שישי 10 ביולי 2020
שאלות
דף ראשי  תגבור  שאלות גרסה להדפסה

שאלות 1-4

 

  1. בנו מכונת טיורינג המחשבת f: N®N המוגדרת על ידי: f(m, n)=max(m, n).

(m ,n ותוצאת הפלט מיוצגים אונרית).

 2.בנו מכונת טיורינג המחשבת {1,0}→*{1,0}::g המוגדרת על ידי:

               המספר שייצוגו הבינארי w מתחלק ב- 3 ,        1

                                                                                    g(w)=

                                                         אחרת ,        0

 3.נגדיר מודל חישובי M'  הזהה ל-M פרט לשינוי הבא:

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

4.בנו מכונת טיורינג המחשבת f:N2®N2 , המוגדרת על-ידי: f(m,n) = (n,m). ז"א בהינתן בקלט שני קלטים, הפלט יהיה אותם הקלטים בסדר הפוך.את התרגיל יש לבצע  בסרט אחד. 

     

 

 09-02-04 / 10:40  עודכן ,  29-01-04 / 13:41  נוצר ע"י שמרית דויטש  בתאריך 
 תגבור - הקודםהבא - שאלות 5-8 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 6