נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
מדעי המחשב
RSS UnderWarrior Forums : RSS מדעי המחשב
נושא

נושא: שלוש שאלות במודלים חישוביים.

 שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
גיל
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 22 August 2006 בשעה 22:11 | IP רשוּם
ציטוט גיל
1. נגדיר מחלקת שפות חדשה, A. שפה L שייכת לA אמ" קיימות L1 ב RE וL2 בco-RE כך ש L היא החיתוך של L1 וL2. סמנו את הטענה הנכונה:
א. RE∪co-RE⊆A.
ב. A⊆RE∪co-RE.
ג. גם א. וגם ב. נכונות.
ד. גם א. וגם ב. לא נכונות.

התשובה הנכונה היא א', אבל אני לא מבין מדוע.





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

קבעו לאיזו מחלקה שייכת הבעיה הבאה:
א. R
ב. RE\R
ג. co-RE\R
ד. אף לא אחת מהנ"ל.


התשובה הנכונה היא ב'. אני חושב שאם M בשפה אז אפשר פשוט לרוץ על כל הקלטים במקביל עד שנתקלים בקלט x המקיים את הדרוש, אבל איך אפשר לעקוב אחרי ריצת M עבור אינסוף קלטים? כלומר, לכל קלט x צריך לזכור באיזה כמה פעמים הוא היה בכל מצב ,את זה אפשר לעשות על ידי שימוש במכונת טיורינג מרובת סרטים- סרט אחד לכל קלט, אך איך נדע מראש בכמה סרטים נשתמש? בנוסף אני לא מצליח לחשוב על שום רדוקציה על מנת להוכיח שהבעיה אינה כריעה.





3. נגדיר את השפה הבאה : L={M| M is a Turing Machine and the function implemented by M is computabe}. האם L כריעה?

אין לי פתרון לשאלה הזו. לדעתי הפתרון הוא שהיא כריעה כי היא טריוויאלית- לכל מכונת טיורינג M הפונ' שM מחשבת היא חשיבה כי קיימת מכונת טיורינג שמחשבת אותה וזו M עצמה. האם זה נכון?


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


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 29 August 2006 בשעה 15:36 | IP רשוּם
ציטוט FOGO
שאלה לי אלייך למה אתה מישתמש בזה יש לזה שימוש ביכלל לא ניראה לי.
מה זה ביכלל  מאיפה הדבר הזה אני מציע לך לילמוד מחשבים.
חזרה לתחילת העמוד הצג את כרטיס החבר של FOGO חפש הודעות אחרות של FOGO בקר בדף הבית של FOGO
 
MENTIS
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 29 August 2006 בשעה 15:40 | IP רשוּם
ציטוט MENTIS
ניראה לי שזה קשור למטמטיקה לא למחשבים. 
חזרה לתחילת העמוד הצג את כרטיס החבר של MENTIS חפש הודעות אחרות של MENTIS בקר בדף הבית של MENTIS
 
גיל
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 31 August 2006 בשעה 15:42 | IP רשוּם
ציטוט גיל
שתי התגובות נכתבו בהומור? 
חזרה לתחילת העמוד הצג את כרטיס החבר של גיל חפש הודעות אחרות של גיל בקר בדף הבית של גיל
 

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

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