TM as a Computational Model
Definition: Let M = (Q, S, G, R, s, F) be a TM;
n-place function f is computed by M provided that
sDx1Dx2…Dxn |–* fDy with  f Î F if and only if
f(x1, x2,…, xn) =  y.
Illustration:
x1
s
D
…
D
x2
xn
D
…
D
D
D
y
f
D
D
…
D
f(x1, x2,…, xn) = y
17/45