פתרון שאלה 9
נוכיח כי התוכנית הבאה שקולה למכונת הטיורנג שתוצג בהמשך:
הרעיון:
נגדיר מכונת טיורינג M שתכיל סרט קלט אחד (שלא ייעשה בו שימוש), ו-3 סרטי עבודה כנגד שלושת המשתנים שבתוכנית: X,Y,Z בהתאמה.
המכונה תהיה מורכבת ממספר מצבים (לפחות כמספר שורות הקוד).
טבלת המעברים של M:
מצב
אות
מצב חדש
פעולה
הערות
פעולה
L1
#,#,#,#
write.1.1
#,#,R,#
נכתוב 3 אחדים בסרט של X
1) X=3
write.1.1
#,#,#,#
write.1.1
#,#,1,#
כתיבת 1 ראשון
write.1.1
#,#,1,#
write.1.2
#,#,R,#
תזוזה
write.1.2
#,#,#,#
write.1.2
#,#,1,#
כתיבת 1 שני
write.1.2
#,#,1,#
write.1.3
#,#,R,#
תזוזה
write.1.3
#,#,#,#
write.1.3
#,#,1,#
כתיבת 1 שלישי
write.1.3
#,#,1,#
L2
#,R,R,#
תזוזה של ראש X ימינה, והכנת סרט Y
L2
#,#,#,#
L2
#,1,#,#
כתיבת 1 בסרט Y
L2
#,1,#,#
L3
L,R,R,#
תזוזה לקצה Y חזרה לשטח X לקראת הפקודה הבאה, והכנת Z
L3
#,#,1,#
L3
1,#,1,#
העתקת 1 מ X ל Y
3) Z=X
L3
1,#,1,#
L3
R,#,L,#
תזוזות
L3
#,#,#,#
L4
L,#,#,#
חזרה לשטח Z לפקודה הבאה
L4
#,#,#,#
L8
#,#,#,#
אם סרט Z ריק, כלומר Z=0
4) IF Z=0 THEN GOTO 8
L4
1,#,#,#
L5
R,#,#,#
סרט Z לא ריק לכן ממשיכים הלאה
L5
#,#,#,#
L5
#,1,#,#
הוספת 1 לסוף סרט Y
5) Y=Y+1
L5
#,1,#,#
L6
R,L,#,#
L6
1,#,#,#
L7
#,#,#,#
הורדת 1 מסוף סרט Z
6) Z=Z-1
L7
#,#,#,#
L4
L,#,#,#
7) GOTO 4
L8
#,#,#,#
H
#,#,#,#
8) End