Problem Solving in Automata, Languages, and Complexity

264 COMPUTABUJTY THEORY

(1) Set (1: := E.

(2) If f(x) < 2” then go to step (3);

(3) Let x :-x + 1 and go to step (2).

otherwise, halt with output x.

By the Church-Turing Thesis, this DTM Tm exists. Note that the functions

f and eq(m) = 2” are fixed and so Tm depends only on m.. Let s(m) be the

code of Tm; that is, Tm = MS(,). We claim that for large m, s(m) < 2m, and

this leads to a contradiction: If s(m) < 2m and if 1M,(m)(&) = x1, then, by the

definition of f, f(x) < s(m) < 2”. However, by the construction of 1M,(m),

we know that the out&t x of AJs(m)(E) must satisfy f(x) > 2”.

To complete the proof, we need to prove the claim. We note that the

machine MS(m) can be constructed in the following way:

(1) It contains two subprocedures Mf and MexJ’ that compute the functions

f and exp, respectively. (Note: These subprocedures are independent

of m.)

(2) It stores m as a constant in the binary form by [log2 ml states. (More

precisely, machine A4s(m) first uses [log, ml special states to write down

m on the tape before it begins the simulation of exp and f .)

(3) It uses a fixed number of tape symbols (independent of m).

The above shows that the size (the number of states) of machine Tm is

bounded by cl + log2 m for some constant cl > 0. Note that a DTM of k

states and using e symbols has at most k l e instructions and so the length of

its code is bounded by czk!(lc + e) f or some constant c2 > 0. Therefore, the

code s(m) of MS(m) is bounded by 2c3(cl+10g2 m)2 for some constant cs > 0. It

is easy to see that for large integers m, s(m) < 2m. This completes the proof

of the claim. cl

Proof2. Assume that f is recursive. Define a function

dY, m> = (minx)[f(x) > ml*

Note that f is a one-to-one function and so is unbounded (i.e., for any constant
Ic, there exists some x such that f(x) > k). Th ere f ore, g is a recursive function.
By the recursion theorem, there exists a constant e such that

b(Y) = !J(Y7 e> = (minx) [f(x) > el*

Since g is recursive, +e is also recursive. Suppose +e(E) = x0. Then, by the

definition of g, we know that f(xo) > e. However, by the definition of f, we

must have f (x0) < e. - This is a contradiction.^0

The above question is closely related to the theory of program-size complex-

ity, or, Kolmogorov complexity. Namely, define the program-size complexity

K(x) of a string x E (0, 1}* to be the size of the minimum-size Turing ma-

chine A4 that prints x on the input E. Then, it is easy to adopt the above