נוכיח כי הטענה נכונה.

תהי מכונת טיורינג M', M'=(S,K,s,H,d'). המכונה גם כותבת וגם זזה בשלב אחד. 

פונקציה ניתנת לחישוב על-ידי M => הפונקציה ניתנת לחישוב על-ידי M':

תהי f פונקציה הניתנת לחישוב על-ידי מכונת טיורינג M=(S,K,s,H,d).

נבנה מכונת טיורינג M'=(S',K',s',H',d') כך ש- S'=S, s'=s, H'=H, K'=K U K'' (K'' תוגדר בהמשך).

נגדיר את d':

 לכל מעבר ב-d מהצורה d(p₁,c₁) = (p₂, R/L) נתאים מעבר ב-d' מהצורה:

 d'(p₁,c₁) = (p₂,c₁,R/L).

 לכל מעבר ב-d מהצורה d(p₁,c₁) = (p₂,c₂) נתאים ב-d' את המעברים:

1.         d'(p₁,c₁) = (p₁₂,c₂,R).

2.        d'(p₁₂,*) = (p₂, *,L).

כלומר: כותבים את האות, עוברים למצב ביניים, וחוזרים חזרה בתזוזה הפוכה.

K'' = כל מצבי הביניים.

הראינו כי כל פעולות d מתורגמות לאותו ביצוע כמו פעולות d' המתאימות, ולכן גם M' מחשבת את f.

פונקציה ניתנת לחישוב על-ידי M' => הפונקציה ניתנת לחישוב על-ידי M:

תהי f פונקציה הניתנת לחישוב על-ידי M': M'=(S',K',s',H',d').

נבנה מכונת טיורינג M=(S,K,s,H,d) כך ש-  S=S', s=s', H=H', K=K' U K''.

נגדיר את d:

לכל מעבר ב-d' מהצורה d'(p₁,c₁) = (p₂,c₂,R/L) נתאים מעברים ב-d (לא ניתן גם לכתוב וגם לזוז ב-d):

1.        d(p₁,c₁) = (p₁₂,c₂)

2.        d(p₁₂,c₂) = (p₂,R/L)

הערות:

1.        כל מצבי p_ij  (מצבי הביניים) הנ"ל יהוו את K''.

 2.    המכונה החדשה אינה חזקה יותר מהמכונה המקורית. כל דבר במכונה החדשה ניתן לבצע

גם במקורית.