מכונת טיורינג למנייה
דוגמא: מ"ט למנייה של {a}*
1) כתיבת $ בסרט 1.
2) תזוזה ימינה בסרט 2 וכתיבת a.
3) שמאלה בסרט 2 עד ה-#, ומשבצת אחת ימינה בסרט 1.
4) העתקת a-ים מסרט 2 לסרט 1 עד ל-# בסרט 2.
5) כתיבת $ בסרט 1 וכתיבת a בסרט 2.
6) חזרה לשלב 3.
משפט: תהי L שפה. קיימת מ"ט M שמקבלת את L אמ"ם קיימת מ"ט C למנייה של שפה
שמונה את L.
הוכחה:
מנייה ← קבלה: תהי C מ"ט שמונה את L . נבנה מ"ט M שמקבלת את L .
M תפעיל את C. אחרי כל כתיבה של מילה u בפלט של C, נבדוק האם w=u.אם כן,
המכונה תעצור, אחרת ניתן ל-C להמשיך לפעול. אם C עוצרת,M נכנסת ללולאה אינסופית.
קבלה ← מנייה: אם M לא עוצרת על u, אז לכל i, M לא עוצרת על u ב-i צעדים,
וממילא C לא תכתוב u בפלט.