abstract model for digital computers in general. Since the primary purpose of a
computer is to transform input into output, it acts as a transducer. If we want to
model computers using Turing machines, we have to look at this aspect more
closely.
The input for a computation will be all the nonblank symbols on the tape at
the initial time. At the conclusion of the computation, the output will be
whatever is then on the tape. Thus, we can view a Turing machine transducer M
as an implementation of a function f defined by
,
provided that
for some final state q f .
Definition 9.4
A function f with domain D is said to be Turing-computable or just
computable if there exists some Turing machine M =(Q,Σ,Γ,δ,q 0 , ,F)such that
for all w ∈ D.
As we will shortly claim, all the common mathematical functions, no matter
howcomplicated, are Turing-computable. We start by looking at some simple
operations, such as addition and arithmetic comparison.
Example 9.9
Given two positive integers x and y, design a Turing machine that computes x +
y.
We first have to choose some convention for representing positive integers.
For simplicity, we will use unary notation in which any positive integer x is