שאלה בחישוביות ומורכבות החישובים.

[y oh why]

שאלה בחישוביות ומורכבות החישובים.

ניסיתי לפתור את השאלה הזאת לבדי ולא הצלחתי.... נתונה לנו מכונת מונים (מכונה שבה ניתן להוסיף אחד, להחסיר אחד, ולקפוץ לתווית עם ערכו של מונה שונה מאפס), ונתון לנו שבמכונה מונים הזאת אין לולאה בתוך לולאה (כלומר, בין If לבין התווית של ה-If אין עוד If באמצע), צריך להוכיח שלא יתכן שמכונת המונים הנתונה מחשבת את ערכו של x בריבוע.... תודה מראש.....

 

[vinney]

אתה תמיד יכול ללכת על דרך השלילה ולהגיע

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

 

[y oh why]

אס"ד = אוטומט סופי דטרמיניסטי? ../images/Emo13.gif

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

 

[y oh why]

אם דיברת על אוטומט סופי דטרמינסטי אז אני

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

 

[y oh why]

כעקרון, מה שאני מתכנן לכתוב זה דבר כזה:

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