הוכחת המשפט

כהקדמה להוכחה נצטרך להגדיר את הסרט הבא: סרט המחולק למספר מסלולים, כלומר כל תו בסרט הוא למעשה טור של אוסף תוים.

דוגמא:

התו הראשון בסרט הוא השלישייה s,#,q .

התו השני בסרט הוא השלישייה f,e,e . וכן הלאה. 

כעת נעבור להוכחה:

המכונה M היא מקרה פרטי של המכונה N . מציבים K=1 וסיימנו.

לכן נוכיח את הכיוון השני:

 נבנה את המכונה M שתבצע סימולציה של פעולות N כל צעד.

הרעיון: נחלק את הסרט של M ל- 2K מסלולים. המסלול ה- 2I-1 יכיל את תוכן הסרט ה-I של N  והמסלול ה- 2I יסמן את מיקום הראשבסרט ה- I .

וכעת לאלגוריתם:

1) נזיז את תוכן הסרט משבצת אחת ימינה, ונוסיף $ בקצה השמאלי.

דוגמא: אם תוכן הסרט הוא baa  , אזי בשלב זה הסרט יראה כך:

 כמובן, שאחרי המחרוזת יש אינסוף #-ים.

 2) נסרוק את הסרט מימין לשמאל (עד $) ונפריד ל- 2K מסלולים,כאשר במסלול הראשון נכתוב את תוכן הסרט הקיים, במסלול השני נכתוב X במשבצת הראשונה, במסלול 2I-1 (עבור I> 1 ) נכתוב #,

ובמסלול 2I, נכתוב X במשבצת השמאלית ביותר, ו- # בשאר המשבצות.

נחזיר את הראש קורא- כותב למשבצת מימין לחלק המופרד למסלולים.

בדוגמא שלנו זה יראה כך:

#	#	a	a	b	#	$
	x
	#	#	#	#	#
	#	#	#	#	x

בסוף שלב זה הראש יצביע על ה-# הימני ביותר (העליון, שמתחתיו אין שום תו).

3) את ה- CPU של המכונה M נחלק למספר אוגרים:באוגר state נכתוב s , ובאוגרים tape i , נכתוב *. 

4) סריקה של הסרט מימין לשמאל ( עד $ ) תוך כדי מילוי tape i, ז"א מה שמעל X נשים באוגרים. 

5) תוך כדי התייעצות בטבלת מעברים של N ועל סמך תוכן האוגרים state ו- tape i , נכתוב תוכן האוגרים state  ו- action i , כאשר i רץ בין 1 ל- k .

  

הטבלא N היא סופית, לכן היא יכולה לקבוע באופן חד- ערכי את הטבלא   של M

6) מעבר לצד ימין של החלק המופרד למסלולים.

7) עבור i=1....k

א. סריקה מימין לשמאל עד ה-$ וביצוע הפעולה action i ,על סרט i.

כל זה צעד בודד של המכונה N

ב. אם state=h, אזי: להוריד $ מהקצה השמאלי, למחוק מסלולים נוספיםולהשאיר מסלול ראשון בלבד, להעביר את הראש למיקום ה X במסלולהשני, למחוק X ולעצור. 

ג. אם באחת מהפעולות של action i יש נסיון להזיז X ל-$, אזי המכונהM עוברת שמאלה,

 משמאל ל-$ ויש נפילה של המכונה. 

8) כתיבת * באוגרים tape i וחזרה לשלב 4.

מקרה של לולאה אינסופית אין צורך לבצע דבר,היות ו-M מבצעת   סימולציה ל-N