Problem Solving in Automata, Languages, and Complexity

5.4 Reducibility 249

Theorem 5.28 (S-m-n Theorem). For each pair of integers m, n > 0, there

is a primitive recursive function sk : ((0, l}*)n+l + (0, l}* such that

Proof. Intuitively, s\ is a function that reads a TM code e and n strings

t1, l l. , t, as inputs and outputs a new TM code e’ such that & simulates
A& on n + m inputs (xl,... , xxfm, ~1,... , yn) as follows: It reads m strings
as the first m inputs to A& and then uses the constants tl,... , t, as the
last n inputs to A&. It is probably easier to understand it in a high-level
programming language environment: Assume the program e is of the form

read(x& read(x&... ; read(x,);

read(y& read(y2);... ; read(

w;

Then, the program e’ = sk(e, tl,... , tn) is as follows:

read(x& read(x&... ; read(x,);

Yl := t1; y2 := t2;.. .; yn := t,;

w;

It is easy to see that the mapping from the program e to e’ is recursive. In

the following, we show that this mapping is actually primitive recursive in the

Turing machine programming system.

We prove the theorem by induction on n. First we consider the case n = 1.

The function sh takes as the input a DTM code e and a string y E (0, l}*

and outputs a DTM code x such that Mz on inputs (xl,... , xm) outputs the

same value as &!e on inputs (21,... , Xm, y).

Assume that lyl =Kandy=yry2*= l yk, whereeach yj, 1 <j - < - Qsasym-

bol in (0, 1). Al so assume that A,& uses states 41,... , qt (i.e., maxstate = t).

Then, A& contains the following instructions:

(i) All instructions of A&, with 41 changed to qt and qt changed to qt+k+l;

(ii) q41, B) = (qt+1A R);

(iii) J(qt+i- 1, B) = (qt+i, yi-I, R), 2 < - i < - k

(iv) S(qt+k, B) = (qt, Yh R).

Thus, the effect of instructions in groups (ii), (iii) and (iv) is to change the
configuration from
(417 XlBX2B l ’ l BXmB)
to
(qty XlBX2B l l l BXrnByB), -
and the instructions in group (i) allow us to simulate A& on this last config-
uration.
Define a function g : ((0, 1})3 -+ (0, l} as follows: