Re: Mathematical Model of GLUTs and Lookups

From: Stuart Armstrong (
Date: Wed Apr 02 2008 - 05:45:36 MDT

Hum, my understanding of a GLUT was that you fed it the state of a
system, and it would give you the next one. Thus a GLUT is a function
on the states of a system; you feed it one state and it gives you

So S is my set of states (taken to be polynomials, for this example),
and G is a GLUT on S - a function from S to itself.

(note: I don't actually want G to be full GLUT, but actually a simpler
rule, like differentiation; but we'll have to start with G being a

G is therefore a collection of ordered pairs of elements of S (the
pairs are (initial state , resulting state). The KC of such a
collection is well defined.

Now R is a rule, i.e. a restiction that the function G must obey. It
is given by an ordered collection of sets (P(n) = the "n-th degree
polynomials"), and the rule that G must map P(n) to P(n-1)).

Now the maximal KC that G can have, given this rule, is huge.
Formulating the rule R itself is of trivial KC; the process of taking
a polynomial and sending it to its degree is also of trivial KC. In
fact I have just, completely defined it in a few sentences, no matter
what the cardinality of S is.

Now we have a hash function f, mapping bijectively to the set f(S). By
the composition f G f^{-1} , we have a function (a GLUT) mapping f(S)
to itself. I called it f(G).

We also have the "rule" f(R). This is given by the requirement that
f(G) must map f(P(n)) to f(P(n-1)). That statement is of trivial KC.
But given an element p of f(S), knowing whether it is in f(P(n)) is of
very high KC: to do so, we need to calculate f^{-1}(p), and the KC of
f is maximal.

Thus the rule f(R) is of high KC, as it requires a lot of information
to describe.

With me so far?


PS: will continue in a later message

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:02 MDT