Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 331

Functions of Several Variables

This subsection defines a computable functionf(n 1 ,n 2 ,...,nk)ofkvariables. First we need to represent
the listm=(n 1 ,n 2 ,...,nk)in our alphabetA.

Definition 13.15: Each listm=(n 1 ,n 2 ,...,nk)ofkintegers is represented by the tape expression

〈m〉=〈n 1 〉B〈n 2 〉B···B〈nk〉

For example,〈( 2 , 0 , 4 )〉= 111 B 1 B 11111 = 13 B 11 B 15.

Definition 13.16: Afunctionf(n 1 ,n 2 ,...,nk)ofkvariables is computable if there is a Turing machineMsuch
that, for every listm=(n 1 ,n 2 ,...,nk),Mhalts on〈m〉and

f (m)=[term(α(〈m〉))]

We then say thatMcomputesf.

The definition is analogous to Definition 13.14 for one variable.

EXAMPLE 13.5 The addition functionf (m, n)=m+nis computable. The input isW = 1 m+^1 B 1 n+^1.
Thus we need only erase two of the 1s. A Turing machineMwhich computesffollows:

M={q 1 ,q 2 ,q 3 ,q 4 }={s 01 Bs 1 R, s 11 BsHR, s 1 BBs 2 R, s 21 BsHR}

Observe that:

(1)q 1 erases the first 1 and movesMto the right.

(2) Ifm=0, thenq 2 erases the second 1 and haltsM.

(3) Ifm=0,q 3 movesMto the right past the blank spaceB.

(4)q 4 erases the 1 and haltsM.

Accordingly, ifm=0 we have:

s 01 m+^1 B 1 n+^1 →s 11 mB 1 n+^1 →sH 1 m−^1 B 1 n+^1

but ifm=0 andm+n=n, we have

s 01 B 1 n+^1 →s 1 B 1 n+^1 →s 21 n+^1 →sH 1 n

ThusMcomputesf (m, n)=m+n.

SolvedProblems

FINITE STATE MACHINES

13.1. LetMbe the finite state machine with state table appearing in Fig. 13-4(a).

(a) Find the input setA, the state setS, the output setZ, and the initial state.

(b) Draw the state diagramD=D(M)ofM.

(c) Supposew=aababaabbabis an input word (string). Find the corresponding output wordv.

(a) The input symbols are on the top of the table, the states are listed on the left, and the output symbols appear in

the table. Thus:

A={a, b},S={s 0 ,s 1 ,s 2 ,s 3 },Z={x, y, z}

The states 0 is the initial state since it is the first state listed in the table.