מבחן מסכם
בנו מכונת טיורינג המקבלת את השפה המכילה את המילה הריקה בלבד
תהיינה 2L, 1L שפות מעל אותו אלפבית. הוכיחו כי אם 2L, 1L ניתנות להכרעה ,
גם 2L Ç 1L ניתנת להכרעה.
הוכיחו כי הפונקציה C11 :N->N , C11(x)=1היא פונקציה פרימיטיבית רקורסיבית
הוכיחו כי sign: N->N ,
sign(x)= x=0 0
x>0 1
היא פונקציה פרימיטיבית רקורסיבית
הוכיחו כי log2x=ëlog2xû (עיגול כלפי מטה של log על בסיס 2) היא פונקציה פרימיטיבית
הגדרה: שפת תכנות ברמה הנמוכה ביותר צריכה לכלול את המרכיבים הבאים:
1. השמת קבוע 2. השמת משתנים 3. הסתעפות מותנית- if 4. הסתעפות בלתי מותנית- go to
5. פעולות אריתמטיות בסיסיות 6. מערכים.
כל פרוצדורה או תוכנית בשפת התכנות שמטרתה לבצע חישוב כלשהו, תהיה שקולה למכונת טיורינג. משתני הפרוצדורה יהיו שקולים לסרטים נפרדים. שם המשתנה יהיה שם הסרט. מערכים יהיו אינסופיים, זאת אומרת ניתנים להגדלה עד אינסוף.
כתבו טבלת מעברים של מכונת טיורינג השקולה לפרוצדורה הבאה:
)X=31
Y=1(2
3)Z=X
4)If Z==0 then go to 8
5)Y=Y+1
6)Z=Z-1
7)Goto 4
8)End
האם השפה {P עוצרת על "ישראל" HIsrael= { P| ניתנת להכרעה או לא?
{P עוצרת על w תוך לא יותר מ- k צעדים | (P,w,k) } = Hk_stop
האם שפה זו ניתנת להכרעה?
גולשים מקוונים: 5