ABA


"|חישוביות| הלכתי קצת לאיבוד עם אחת השאלות. אשמח להכוונה"
גירסת הדפסה        
קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #10023 מנהל    סגן המנהל    מפקח   Winner    צל"ש   מומחה  
אשכול מספר 10023
Zippo 
חבר מתאריך 26.5.02
7921 הודעות
   15:47   13.08.10   
אל הפורום  
  |חישוביות| הלכתי קצת לאיבוד עם אחת השאלות. אשמח להכוונה  
 
אני לוקח קורס קיץ בחישוביות, כדי להוריד מהעומס בשנת הלימודים הקרובה.
קיבלנו שאלה לא פשוטה בכלל, ואני לא ממש יודע איך להתמודד איתה.
אשמח להכוונה (ועדיף רק הכוונה, כך שברגע שאבין את הרעיון, אוכל לפתור בעצמי) לגבי השאלה.

מדובר בשאלה 4, סעיף ג:
http://yairdombb.com/courses/comp2010s/Ex04.pdf

כמו כן, הגדרנו מכונת טיורינג כ"שביעייה" (Q,Σ,Γ,δ,q_0,q_acc,q_rej)
ולכן הקבוצה TM עבור הערכים 0,1,2 היא קבוצה ריקה (מפני שכל מכונה מכילה לפחות את המצבים q_0,q_acc,q_rej),
ויש צורך לתקן קצת את השאלה, ולהגדיר שבמקרים הספציפיים הנ"ל, הפונקציה BB מחזירה 0.

זה לא אמור לשנות לגבי סעיף ג', התיקון הוא רק בשביל הגדרת השלמות.

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

תודה רבה, ושבת שלום.


                                שתף        
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

  האשכול     מחבר     תאריך כתיבה     מספר  
  לא חשוב, פתרתי. אפשר למחוק... Zippo  13.08.10 16:35 1
  מכתב Deuce  13.08.10 17:29 2
     הצלחתי לפתור בכוחות עצמי :) Zippo  16.08.10 20:59 3

       
Zippo 
חבר מתאריך 26.5.02
7921 הודעות
   16:35   13.08.10   
אל הפורום  
  1. לא חשוב, פתרתי. אפשר למחוק...  
בתגובה להודעה מספר 0
 


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
Deuce 
חבר מתאריך 1.9.08
6225 הודעות
   17:29   13.08.10   
אל הפורום  
  2. מכתב  
בתגובה להודעה מספר 0
 
Busy Beaver היא פונקצייה לא חשיבה ידועה במדעי המחשב. אני יכול לסייע לך בעצמי, אם כי אני בטוח שתוכל לקבל את הסיוע מויקיפדיה:
http://en.wikipedia.org/wiki/Busy_beaver






                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
Zippo 
חבר מתאריך 26.5.02
7921 הודעות
   20:59   16.08.10   
אל הפורום  
  3. הצלחתי לפתור בכוחות עצמי :)  
בתגובה להודעה מספר 2
 
בסה"כ, כמו בהוכחה של אי כריעות בעיית העצירה, כאשר כותבים תוכנית שמשתמשת בתוכנית נתונה שהנחנו עליה בשלילה כי היא מכריעה את הבעיה, ומראים שבהכרח נוצרת סתירה\פרדוקס, על אותו רעיון פתרתי את השאלה הנ"ל.
פשוט הנחתי שיש תוכנית שמחשבת אותה, והראיתי שאני יכול להשתמש בה כדי ליצור סתירה.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

תגובה מהירה  למכתב מספר: 
 
___________________________________________________________________

___________________________________________________________________
למנהלים:  נעל | תייק בארכיון | מחק | העבר לפורום אחר | מחק תגובות | עגן אשכול
       



© כל הזכויות שמורות ל-רוטר.נט בע"מ rotter.net