Problem Solving in Automata, Languages, and Complexity

216 TURING

Example 4.39 Show that if a set A can be expressed as

(3m)R(n, m)} for some recursive predicate R, then A is r.e.

quence,

(a) F = {n 1 n - > 2, (3a, b, c > - 1) an + b” = cn} is r.e.3

MACHINES

A = {n 1

As a conse-

(b) For any recursive function f, the set Jf = {n 1 n > - 1, (3m) f cm) (n) = 1)

is r.e.4

Proof. This result follows from

CA b) = neg(neg(l+ ( minm)R(n, m))).^0

To compare partial recursive functions with Turing-computable functions,
we need to extend the notion of partial recursive functions to functions defined
on strings.
For any fixed alphabet C = {sl , ~2,... , sk}, with a fixed ordering s1 4

s2 4 l * -( sk on its elements, the lexicographic ordering -( on strings in C

can be defined as follows: Let IZ: = 33x2. l l xm and y = yly2 l l l yn , where each

xiandeachyj, 1 < _ i < _ m, 1 < _ j < _ n, is a letter in C. We say x + y if

(a) I4 < IYI ( i.e., m < n), or

(b) Ixl= 1~1 and (3i)l<i<n[xl -- = YI~-~~~x~-I = yi-1,~; 4 yi]-

Then, the set C*, written in the lexicographic ordering, is

{E, Sl, s2, l l l ,Sk,SlSl,SlS2, l l + ,slsk,s2s1, l l l ,SkSk,SlSlSl, l l l )e

From this ordering on C*, we define a one-to-one, onto function LX : N +

C* such that Lc(n) is the nth string in C* under the lexicographic ordering

(starting with LX(O) = E). When the alphabet C is understood, we simply

write L for Lx.

Theorem 4.40 Assume that c = {sI,s~,... , sk} and s1 -( s2 -(... -( sk.

Then, for each string x = si,sinal... sil sa,, we have

L-l ( x > = in ’ k” + in-1 l /in-l + ” ’ + il ’ k + io.

Proof. We can prove this relation by induction on strings x. First, if x = E

then ~-l (x) = 0 and if x = s1 then ~-l(x) = 1.

Next, assume that x = sa,sinwl... silsiO, with n > 0, and L-‘(X) = i, l

k” + in-1 ’ k”-l + l ** + il l k + io, and consider thesuccessor y of x in C*

under the lexicographic ordering 4. There are two possible cases.

3The famous Fermat’s Last Theorem states that F = (2) and so F is actually recursive.

4Let f(n) = 3n +^1 if n is odd, and f(n) = n/2 if n is even. The (3n+ 1)-conjecture

states that Jf consists of all positive integers.