שאלה במודלים חישוביים.
צריך להוכיח שהשפה הבאה לא רקורסיבית לפי משפט רייס:
צריך להוכיח שהשפה הבאה לא רקורסיבית לפי משפט רייס:
L={M | M is a Turing machine and ∃x such that M halts on x}
ז"א, צריך להוכיח לפי משפט רייס שהבעיה הבאה אינה כריעה: קלט: מכונת טיורינג M. שאלה: האם יש קלט שעליו M עוצרת. הסתבכתי עם ההוכחה: ברור שהיא לא טריוויאלית. תהיינה M1, M2 מ"ט כך ש L(M1)=L(M2)zzz. אם קיים x כך שM1 עוצרת עליו, אז אם הוא ב L(M2) zzz אז גם M1 תעצור עליו, אבל אם L(M1)=∅=L(M2) zzz אז ייתכן שM1 עוצרת על x (דוחה אותו) ו M2 היא מכונה שנכנסת ללולאה אינסופית עבור כל קלט. אפשר עזרה בבקשה? תודה מראש.