שאלות 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:N²®N² , המוגדרת על-ידי: f(m,n) = (n,m). ז"א בהינתן בקלט שני קלטים, הפלט יהיה אותם הקלטים בסדר הפוך.את התרגיל יש לבצע  בסרט אחד.