מכונת טיורינג

[אלוהים1980]

מכונת טיורינג

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

 

[ahab]

תחשוב קצת...

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

 

[DadleFish]

לקח לי כמה שניות להבין מה זה לעזאזל

ייצוג אונארי... בקיצור, אתה צריך לעשות strlen. שאלה יפה, בדיוק פתרתי אותה בקורס שלי לפני שבועיים בערך

יש בגדול שתי שיטות, אחת ב-nlogn והשניה ב-n^2. תחשוב על התהליך של המרת מספר דצימלי לבינארי (זו השיטה היעילה יותר).

 

[DadleFish]

אה, ועוד שתי הערות -

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

 

[ahab]

לא חוכמה ../images/Emo13.gif

הרי אפשר להוכיח שקילות בין מכונה עם K סרטים לבין מכונה עם סרט אחד

 

[DadleFish]

נכון,

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

 

[מיכל דביר]

נכון, אבל

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

 

[DadleFish]

לא יודע, למען האמת -

במכללה שלי לא מפנקים אותנו ביותר מסרט אחד

 

[אוֹריארד]

דווקא...../images/Emo26.gif

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

 

[DadleFish]

אם הבנתי אותך נכון,

אתה פותר את זה ביעילות של n בריבוע. אבל יכול להיות שהבנתי אותך לא נכון

 

[אוֹריארד]

*אני* פותר את זה ב-O של 1 דווקא

אני פשוט הולך, משיג רפרנס ממישהו ומצלם... (בהנחה שאורך התרגילים פחות או יותר קבוע - זה יוצא O של 1).

 

[אלוהים1980]

ואיך הולך לך אחר כך במבחן?

 

[אוֹריארד]

איזה מבחן?? יש לי עדיין "לא השלים"!

 

[אלוהים1980]

טוב, בתרגול קיבלנו הדגמה,

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

 

[ahab]

יעילה??

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

 

[אלוהים1980]

טוב, נראה לי שזה מה שאעשה. תודה.

 

[DadleFish]

לא נכון,

האלגוריתם שהוא תיאר רץ ב-N בריבוע, והיעילות היא חשובה גם (ובמיוחד!) במכונת טיורינג. יש אלגוריתם שרץ ב-nlogn, וזה לא האלגוריתם הזה.

 

[ahab]

למה N בריבוע?

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

 

[DadleFish]

פספסת את הריצות על הסרט הלוך ושוב

תראה, איטרציה אחת מטפלת בספרה אחת. מכאן שיש N איטרציות. כל איטרציה צריכה לרוץ על הסרט - בוא נניח שהסכום עומד לימין המחרוזת, ובכל פעם אתה מוריד ספרה מימין המחרוזת. זה יוצא logn+1 צעדים באיטרציה הראשונה, logn+2 לשניה, וכו' עד logn+n צעדים בסוף. סה"כ זה nlogn+סכום הסדרה החשבונית 1..n - בסה"כ n בריבוע אירטציות. עכשיו, מסתבר שכל פעולה שהיא - כלומר, כל איטרציה - לוקחת n פעולות. עם זאת, יש פתרון שלוקח logn איטרציות ולא n איטרציות. זה הפתרון היעיל, שלוקח nlogn פעולות.

 

[ahab]

צודק..

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