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