Problem Solving in Automata, Languages, and Complexity

(^250) COMPUTABILITY THEORY
(a) If i = 0, then g(e, y, i) is the code of instructions of A& in part (i);
(b) If 1 < i < k + 1, then g(e, y, i) is the code of the ith instruction in part
(ii)-&) r
(c) If i > k + 2, - then g(e, y, i) = 0.
It is not hard to see that g is primitive recursive.
2 < i < - - k, g(e, y, i) can be expressed as
For instance, for the case
if substr(y, i 1. 1, 1) = 0 then 10t+i-110310t+i101021
else 10~+i-110310~+i1021021.
For case (a), s(e, Yt 0) can be obtained from e by replacing each substring lot1
that represents state qt by the string 10 ‘-~+ll, and replacing each substring
101 that represents state ~1 by the string 10tl. By Exercise l(b) of Section
5.1, it is primitive recursive.
Using function g, we can show that s& (e, y) is primitive recursive. We first
define a new function s’ that concatenates all instructions of g(e, y, i):
s’(e, Y, 0) = substr(g(e, Y, 0)) 1, Is(e, Y, o)l - 2))
s’(e, y, i + 1) = c0ncat2(s’(e, y, i),g(e, y, i + 1)).
Then, it is clear that s&(e, y) = cancat2(s’(e, y, 1~1 + l), 11) and is primitive
recursive.
The above proved the case n = 1 (with respect to arbitrary nz > 0). For
the general cases n > 1, we define
s, n+l (e,Yl,‘,Yn+l) = s~(s~+n(e,Y~+l),Yl,...,Y,)
and verify that

-

4

- m+n

S&+ (%Y?-L+ 1

• f+F _

Therefore, the function sk+’ satisfies the desired property. q

Using the s-m-n theorem, we can present a more complete, and more ele-

gant, proof of the reduction K’ <m - EMP:

Example 5.27 (R evisited) Show, by the s-m-n theorem, that Ii: Lrn EMP.

Proof. First, define a function

1 if x E 1C

g(y’ z> = { T otherwise.