אלגוריתם השקילות

למכונה B יש שלושה סרטים: סרט קלט, סרט עבודה, סרט בחירות- choises. B תבצע סימולציה של המכונה A . state ישמור את המצב של המכונה שאנחנו מבצעים לה סימולציה. סרט העבודה יהיה כאילו הסרט של המכונה שאנו עושים לה סימולציה.

פעולות  המכונה B:

1)       כותבת $ בסרט העבודה, וזזה ימינה.

2)       זזה ימינה משבצת אחת בסרט הבחירות.

3)        מעתיקה קלט מסרט הקלט לסרט העבודה, אחרי ה-$.

4)        כותבת SA  באוגר state.

5)        מפעילה את המכונה MP על סרט הבחירות.

עכשיו אנחנו מוכנים לבצע את הסימולציה:

6)        זזה שמאלה משבצת אחת בסרט הבחירות.

7)        כותבת באוגר tape את הסימן שמתחת לראש שבסרט העבודה.

8)        נסמן ב- pair את התוכן של המשבצת שמתחת לראש הקורא בסרט הבחירות. אם pair=# עבור לשלב 9, אחרת בדוק האם ישנו המעבר בטבלת המעברים במ"ט הלא דטרמיניסטית. אם כן: עדכן את האוגר state  בהתאם, ובצע את הפעולה בסרט העבודה וחזור לשלב 6. אחרת המשך לשלב 9.

9)        מחק את תוכן סרט העבודה עד ל-$, עבור לקצה הימני של סרט הבחירות וחזור לשלב 3.

אם בשלב כלשהו התוכן של האוגר state הוא hA, אזי המכונה B עוצרת לחלוטין.

מתקיים:

אם קיים חישוב של A שעוצר על w , אזי קיימת סדרת זוגות p בסרט הבחירות, שתביא את הסימולציה למצב hA והמכונה B תעצור.

ומצד שני, אם A לא מקבלת את w, אזי לכל סדרת מעברים p, הסימולציה לא תגיע למצב hA , וממילא B לא תעצור.