חישוב פונקציה ע"י מכונת טיורינג

הגדרה: תהי *1∑→*2∑:f , ותהי S,h),(Q,S,d M=  מכונת טיורינג , כאשר    S2 È 1S Ê S

נאמר כי M  מחשבת את f  לכל  wÎS1*

(s, #w # )     M*      (h, #, f (w) #^ ).

בחישוב של פונקציה ממספרים טבעיים למספרים טבעיים, נשתמש בייצוג אונרי של המספרים, ז"א המספר  k  ייוצג ע"י המחרוזת:

^k = 111...11

     ↑

    ^{k  פעמים}

הגדרה: תהי  :N →N f  ותהי S,h),(Q,S,d M=  מכונת טיורינג. נאמר כי M   מחשבת את f את לכל  kÍ  N 

מתקיים

 (  #  ^{f (k)}             ( s, #1 ^k # ) ^|------  ( h, #1

דוגמא: f: N→N     

                      2n = f(n)

נשים לב  שה - א"ב  של התשובה זה רק 1. אבל, במכונה הוספנו את A  ואת #  . אלו הם סימונים פנימיים של המכונה, שלא נראה אותם בקלט או בפלט.