נוכיח את הצד השני:

הרעיון: בהינתן מ"ט לא דטרמיניסטית A=(QA, ∑A,∆A,sA,hA) נבנה מ"ט דטרמיניסטית

 B=(QB, ∑B,δ B,sB,hB)  שמבצעת סימולציה למכונה A , ומנסה את כל האפשרויות למעברים הלא דטרמיניסטית (כשיש).

נסתכל על הקבוצה P=(QA× (∑AU{R,L}))* זוהי קבוצה של זוגות, כאשר כל זוג מכיל מצב ופעולה.

נגדיר סדר על הזוגות האלו:

עבור p1, p2 ε P נאמר כי p1 הוא לפני p2 ונסמן p1<p2  אם:

1)                p1 קצר מ-p2 , כלומר קצר באורך הסדרה, ב-p1 יש פחות זוגות מב-p2.

      2)                האורך של p1, p2 זהה, ן- p1 מופיע לפני p2 בסדר הלקסיקוגרפי על P.

טענת עזר: קיימת מ"ט דטרמיניסטית MP לכל סדרה pεP . אם נותנים ל- MP את p כקלט,

אזי  MP עוצרת כאשר הסדרה הבאה לפי סדר, בפלט.

כלומר: MP=(QP, ∑P,δP,sP,hP) ן- QA× (∑AU{R,L}) з ∑P (ז"א שחלק מהסימנים של MP

זה זוגות של מצב ופעולה).

מתקיים לכל pεP  ---- (hp,#p'#)|(sp,#p#) p<p'  ובדיוק הבא בתור אחרי p.