תורת החישוביות/מודל לבעיות הכרעה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←שקילות למודל הכללי: קישורים פנימיים |
|||
שורה 44:
נניח שקיימת המכונה
<math>M'</math>
, ובעזרתה נבנה את המכונה M. המכונה תעבוד בעזרת מספר לולאות מקוננות (כל אחת יכולה להשתמש בסרט אחד או יותר, לפי מה
#בלולאה החיצונית ביותר, המכונה תעדכן מונה מספרי רץ <math>n = 0, 1, 2,\ldots</math>
#בלולה פנימית יותר, המכונה תייצר את סדרת המחרוזות <math>\{z | z \in \Sigma^*, |z| \leq n\}</math>.
| |||