שיחה:בעיית הכרעה

הערה לסעיף חישוביות

שאלה לסעיף חישוביות כמו שנכון לומר ש"כל תוכנית מחשב היא רצף סופי של סימנים של שפת תכנות. לכן כל תוכנית מחשב ניתן לקודד כמספר טבעי יחיד", כן נכון הדבר לגבי בעיית ההכרעה עצמה, שאף היא רצף סופי של סימנים של שפת תכנות. ז"א שקבוצת הבעיות היא בעלת אותה עוצמה של קבוצת תכניות המחשב (אלף אפס).

ובאשר להשוואתה לעצמת קבוצת כל התת-קבוצות של הטבעיים, לא הבנתי משתי סיבות (הנחות שלי): (1) כל קלט הוא סופי, כיון שהשפה סופית. ובנוסף, (2) מספר הקלטים המתאימיםן לבעיה גם הם סופיים, בגלל סופיות השפה.

ועכשיו, רק קלקלתי, כי עכשיו כל הקלטים אפילו אינם בעוצמת אלף אפס, לא מדובר בכלל במשהו אינסופי.

גם אם שגיתי באחת משתי ההנחות (במה? למה?), עדיין כל המרכיבים במערכת (התוכניות, הבעיות והקלטים) בעלי עוצמה זהה (אלף אפס). רצוני - שיחה 01:55, 2 בפברואר 2012 (IST)

תקרא שוב את ההגדרה של בעיית הכרעה. אף אחד לא דורש ממנה שיהיה ניתן לתארה כרצף סימנים בשפה. למה שמספר הקלטים המתאימים לבעיה יהיה סופי? הבעיה "האם n זוגי" היא בעיית הכרעה שמסוגלת לקבל אינסוף קלטים. דניאל • תרמו ערך 16:54, 13 בפברואר 2012 (IST)

תוכל להסביר לי כיצד תיתכן בעיה שלא ניתן לתארה ע"י רצף סופי של סימנים בשפה ? רצוני - שיחה 21:08, 13 בפברואר 2012 (IST)

כפי שמוכח בערך, כל בעיה מתאימה לאיזשהי תת-קבוצה של הטבעיים. וכפי שמוכח בערך, יש הרבה יותר תת-קבוצות של הטבעיים מאשר תיאורים בשפה. לכן רוב התת-קבוצות (כלומר הבעיות) אינן ניתנות לתאור. דניאל • תרמו ערך 22:11, 13 בפברואר 2012 (IST)