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

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

(הטבעיים הזוגיים מודפסים כרגיל)

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

איך אפשר לבנות אנומרטור כזה?

אם אני לא טועה, שפה RE זו שפה שיש מכונת טיורינג המקבלת אותה, נכון?

הרעיון של האלגוריתם הוא כזה:

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

אבל נגיד שדרושים 100 צעדים כדי לקבל את 3 ו-500 צעדים כדי לקבל את 1.

לפי האלגוריתם הנ"ל, 3 יודפס לפני 1, ואנחנו לעומת זאת רוצים להדפיס את 1 לפני 3.

הממ צודק.

למעשה, אין דרך לפתור את זה, אלא אם מניחים R=RE (צריך שהשפה תהיה כריעה ® ולא RE).

הוכחה:

נניח שנתון לנו אלגוריתם שיודע למנות על כל שפה RE בסדר עולה.

כעת, נניח שיש לנו שפה RE כלשהי וקלט n, ואנחנו רוצים להכריע אם n נמצא בשפה. אז יש שתי אפשרויות:

או שהשפה סופית, ואז היא רגולרית ואפשר להכריע בקלות.

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

בקיצור, קיבלנו שהשפה כריעה, כלומר R=RE.

שים לב שדורשים מונוטוניות רק על מספרים אי-זוגיים.

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

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

אז עדיין אין בעיה.

נניח שיש לנו שפה שהיא RE (נקרא לה L1). אז אפשר בקלות להגדיר שפה L2 המוגדרת ע"י

L2 = {n*2+1 | for n in L1}

קל לראות שיש רדוקציה מ-L1 ל-L2 ולהיפך (בשביל לבדוק אם n שייך ל-L1 אפשר לכפול אותו ב-2 ולהוסיף 1 ואז לבדוק אם התוצאה ב-L2, ובשביל לבדוק אם n שייך ל-L2, קודם מוודאים שהוא אי זוגי, ואם כן אז מחלקים אותו ב-2 בלי שארית ובודקים אם התוצאה ב-L1).

כלומר L1 ו-L2 שקולות - אם אחת ב-RE או ב-R אז גם השנייה ב-RE או ב-R. לכן L2 ב-RE.

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

אז L2 ב-R, ולכן גם L1 ב-R.

שכנעת אותי. כנראה שהיתה טעות בשאלה.

תודה רבה על העזרה.

שאלה נוספת,

צריך להפריך את הטענה: בכל שפה אינסופית L מוכלת שפה אינסופית כריעה 'L.

חשבתי ללכת על דוגמא נגדית L = HALT (בעיית העצירה). ואז, בגלל ש'L אינסופית ומוכלת בHALT, להראות שהמכונה של 'L צריכה לכל הפחות להכריע את HALT. האם הכיוון הזה נכון לדעתכם?

לא משנה הסתדרתי.

שאלה אחרונה ואני מסיים להציק לפורום

נתונה בעיה:

נתון קידוד של מכונת טורינג <M> באורך קטן מ100^10. האם M מכריעה את המילה הריקה?

האם הבעיה כריעה?

אני יודע שעבור קידוד כללי הבעיה לא כריעה (למעוניינים, ההוכחה כאן: http://www.cs.williams.edu/~andrea/cs361/Lectures/lect32.pdf )

אבל מה קורה כשאורך הקידוד חסום? כלומר כאשר מובטח לי שלM אין יותר מ-i מצבים או יותר מ-j תוים בא"ב.

האם כעת הבעיה מספיק "קלה" כדי להיות כריעה?

אם השפה L היא "שפת כל הקידודים של מכונות טיורינג שאורכן קטן מ-100^10 והן מכריעות את המילה הריקה", אז השפה היא סופית - ולכן היא לא רק כריעה, אלא רגולרית.

זאת בדיוק הנקודה שאני מסתבך איתה.

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

מה? לא הבנתי את השאלה.

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

תראה למה אני מתכוון.

בעיה אפילו יותר קלה: הקלט הוא תמיד אותו קלט, קידוד של מכונה מסוימת אותה נסמן כM.

בשפה יש מילה אחת (אם M עוצרת על המילה הריקה) או אפס מילים (אם M לא עוצרת על המילה הריקה). בכל מקרה השפה היא סופית. לכן היא רגולרית. לכן היא כריעה.

אבל זה אומר שניתן להכריע אם M עוצרת על המילה הריקה, בסתירה לבעיית העצירה.

לא, זה לא.

בעיית העצירה אומרת כזה דבר:

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

הבעיה שאתה הגדרת היא כזו:

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

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

אני אתן לך דוגמה ממבחן (או תרגיל, לא זוכר) שהיה לי:

תהי M מכונת טיורינג הפועלת באופן הבא: לכל קלט w, אם השערת קולץ' נכונה אז המכונה מקבלת את w, אחרת היא דוחה אותה.

האם השפה של M (נקרא לה L) היא כריעה?

התשובה היא כן - משום ש-M לא תלויה ב-w, ייתכנו רק שתי אפשרויות - או ש-L היא השפה הריקה (אם ההשערה לא נכונה) או שהיא שפת כל המילים (אם ההשערה כן נכונה). אנו לא יודעים איזו משתי השפות היא L, אבל זה לא משנה - שתיהן כריעות.

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

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