תהי S,h),(Q,S,d M= מכונת טיורינג.

קונפיגורציה של M  הינה רביעיה(q,u,a,v)ÎQ x S* x S x S*  :

כלומר:          q ÎQ   מצב

                    u, v   מחרוזות

                    α      סימן

המשמעות:   q - מצב של הבקר המרכזי.

                  u - תוכן הסרט משמאל לראש.

                  a - סימן מתחת לראש.

                 v  - תוכן הסרט מימין לראש, כאשר מימין ל – v יש אינסוף # - ים.

סימון מקוצר:  את הקונפיגורציה (q,u,a,v) נסמן כ - q,u,a,v))

סימון:  תהי S,h),(Q,S,d M= מכונת טיורינג  ויהיו ((q1,u1,a,v1 C1=

ו -  ((q2,u2,a,v2 C2=  קונפיגורציות של M

נסמן: C1       M         C2  

אם המכונה M עוברת מהקונפיגורציה C1 לקונפיגורציה C2 בצעד אחד בדיוק.

נסמן: C1       M *         C2 אם המכונה עושה זאת ב  0 או יותר צעדים.