In particular, I want to see if I can find a lower limit of difficulty for the most difficult functions of a particular type. I thought I had it nailed last night, but as soon as I went to bed I realized I was wrong.

Imagine a computer with the following properties:

1. The computer's only data type is an integer in the set [0..N-1], called an

**int**.

2. The computer's programs represent functions that take two

**int**s and returns an

**int**. The set of all such functions is F.

3. The computer has an instruction set composed of A <= N+2 functions drawn from F. The computer can easily evaluate every function in its instruction set.

4. The computer's programs are finite function trees, so each program has a root function drawn from the instruction set, which takes two parameters. The two parameters of the root function may be function trees, constant

**int**s, or the special symbols

*x*and

*y*which evaluate to the program's two input parameters. There is no recursion.

5. The difficulty of a program is the average number of operations required to evaluate the program for any possible input values

*x*and

*y*.

For simplicity, we initially assume that there is no lazy evaluation.

Given a computer like this, can we put a lower limit on the difficulty of the most difficult function in F?

If there is no lazy evaluation, then the difficulty of a function is proportional to the number of instructions. Given that there are N

^{N2}functions in F, if you could write maximally efficient programs to represent each of those functions, how big would the largest such efficient program need to be?

There are p

_{0}= N+2 distinct programs that could be written with zero instructions. These would be the programs that returned a constant value, or else

*x*or

*y*with no modification.

The number of distinct programs that can be written with one instruction is p

_{1}= A*(p

_{0 }* p

_{0}) = A(N+2)

^{2}. That is, there are A possible instructions, which must take a program with zero instructions for each parameter.

The number of distinct programs that can be written with two instructions is p

_{2}= A*(p

_{0 }* p

_{1}+ p

_{1 }* p

_{0}) = 2A

^{2}(N+2)

^{3}. That is, the first parameter may be a zero-instruction tree, in which case the second parameter must be a 1-instruction tree, or vice-versa.

The number of distinct programs that can be written with three instructions is p

_{3}= A*(p

_{0 }* p

_{2}+ p

_{1 }* p

_{1}+ p

_{2 }* p

_{0}) = 5A

^{3}(N+2)

^{4}. The progression we are seeing here is that p

_{n}= s

_{n}A

^{n}(N+2)

^{n+1}, where s

_{n}is the number of different trees that can be formed with

*n*binary functions.

There will be a lot of overlap in the program space, meaning there will be multiple programs that can evaluate to the same function. This means we can't say that

*n*instructions can always represent p

_{n}functions, but we can say that they will represent

*no more than*p

_{n }functions. Thus, for p

_{n}= |F| = N

^{N2}, we can be certain that the most complex program representing a function in F can be

*no smaller than**n*instructions.

So the lower limit

*d*on the difficulty of the most difficult function in F is calculated as follows:

p

_{d}> N

^{N2}.

s

_{d}A

^{d}(N+2)

^{d+1 }> N

^{N2}.

For large values of

*d*, I think 3

^{d}< s

_{d}< 4

^{d}. This needs to be proven, though. If it is true, we could fudge a bit and say

4

^{d}A

^{d}(N+2)

^{d+1 }> N

^{N2}.

*d ln*4

*+ d ln*A

*+ d ln*(N+2) +

*ln*(N+2)

*>*N

^{2}

*ln*N.

*d ln*4

*+*

*d ln*A

*+ d ln*(N+2)

*>*N

^{2}

*ln*N -

*ln*(N+2).

*d*

*>*(N

^{2}

*ln*N -

*ln*(N+2)) / (

*ln*4 +

*ln*A

*+ ln*(N+2)).

Of course, there is a lot more to gnaw on here, like operation laziness and pre-evaluation, which might be real game-changers. But as we have it now, the difficulty of the most difficult functions in F increases in proportion to N

^{2}.
## No comments:

## Post a Comment