תוכנית מחשב אל מול מכונת טיורינג

[nullity]

תוכנית מחשב אל מול מכונת טיורינג

אני זקוק למעט עזרה במודלים חישוביים. האם שתי הבעיות הבאות נמצאות באותה מחלקה? או שקיים איזה הבדל עקרוני בין השתיים? א. קלט: תוכנית מחשב P שאלה: האם קיימת תכנית קצרה יותר (באורך קוד) המחזירה כנגד כל קלט תוצאה זהה לזו שמחזירה P? ב. קלט: מ"ט M שאלה: האם קיימת מכונה קצרה יותר (באורך הקידוד) המחזירה כנגד כל קלט תוצאה זהה לזו שמחזירה M? תודה

 

[vinney]

איזו מן שאלה זאת?

תגדיר "קצרה יותר"

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

 

[DadleFish]

נראה לי ש-א יותר קלה מ-ב.

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

 

[vinney]

אלדד

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

 

[DadleFish]

נראה לי שהשאלה המקורית מטופשת,

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

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

 

[vinney]

הא, ראית את הכותרת לתשובה הראשונה

שלי?

 

[nullity]

אוקי, סיימנו עם השאלה המקדימה

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

 

[vinney]

אתה יכול לכתוב בדיוק מה נשאלת?

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

 

[מסית ומדיח]

באמת חשוב מה בדיוק נשאלת

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

 

[nullity]

makes sense

תוגה

 

[דודהלי]

שתי השאלות אינן ניתנות לפתרון