שאלה בחישוביות (מכונת טיורינג)
השאלה : מכונת טיורינג למניית שפה (Enumerator) היא מכונה שאינה מקבלת קלט ופולטת את כל מילות השפה . המבנה הכללי של מכונת למניה הוא כדלהלן : המכונה עובדת על 2 סרטים , כאשר על הסרט הראשון מתבצעים כל החישובים הנדרשים , ועל הסרט השני ("סרט הפלט") נכתבות המילים בשפה בזו אחר זו , מופרדות ע"י התו #-לא-שייך-לסיגמא וללא תזוזה אחורה (כלומר מרגע שנכתבה מילה כלשהי לא ניתן למחוק או לשנות אותה בכל דרך) . נאמר ששפה L ניתנת למנייה אם קיימת מ"ט M כלשהי למניית L (כלומר M אינה מקבלת קלט , וכותבת על סרט הפלט שלה את כל מילות L ורק אותן) . הוכיחו שמחלקת השפות הניתנות למנייה שווה למחלקת השפות הניתנות לקבלה . התשובה שכתבתי : עבור כל שפה ניתנת לקבלה ניתן לבנות מ"ט => נוכל להכין מ"ט עם הסרט המקורי לבדיקת המילה מהשפה , והסרטים הנוספים (או סרט אחד) ירשום לאחר מכן במקביל כל מילה (כמובן ללא קלט , אלא נעשה בצורה עקבית ידועה מראש) שתתקבל מהסרט המקורי . התהליך מקביל , ולכן ניתן לקבוע כי מחלקת השפות הניתנות למנייה שווה למחלקת השפות הניתנות לקבלה . האם דרך ההוכחה שלי נכונה? אם לא אשמח לסיוע , תודה מראש...
השאלה : מכונת טיורינג למניית שפה (Enumerator) היא מכונה שאינה מקבלת קלט ופולטת את כל מילות השפה . המבנה הכללי של מכונת למניה הוא כדלהלן : המכונה עובדת על 2 סרטים , כאשר על הסרט הראשון מתבצעים כל החישובים הנדרשים , ועל הסרט השני ("סרט הפלט") נכתבות המילים בשפה בזו אחר זו , מופרדות ע"י התו #-לא-שייך-לסיגמא וללא תזוזה אחורה (כלומר מרגע שנכתבה מילה כלשהי לא ניתן למחוק או לשנות אותה בכל דרך) . נאמר ששפה L ניתנת למנייה אם קיימת מ"ט M כלשהי למניית L (כלומר M אינה מקבלת קלט , וכותבת על סרט הפלט שלה את כל מילות L ורק אותן) . הוכיחו שמחלקת השפות הניתנות למנייה שווה למחלקת השפות הניתנות לקבלה . התשובה שכתבתי : עבור כל שפה ניתנת לקבלה ניתן לבנות מ"ט => נוכל להכין מ"ט עם הסרט המקורי לבדיקת המילה מהשפה , והסרטים הנוספים (או סרט אחד) ירשום לאחר מכן במקביל כל מילה (כמובן ללא קלט , אלא נעשה בצורה עקבית ידועה מראש) שתתקבל מהסרט המקורי . התהליך מקביל , ולכן ניתן לקבוע כי מחלקת השפות הניתנות למנייה שווה למחלקת השפות הניתנות לקבלה . האם דרך ההוכחה שלי נכונה? אם לא אשמח לסיוע , תודה מראש...