Re: Mathematical Model of GLUTs and Lookups

From: Lee Corbin (lcorbin@rawbw.com)
Date: Mon Apr 14 2008 - 19:32:31 MDT


To recapitulate: to avoid "the end of time" or to avoid belief
in "platonia" or having to dismiss (according to my calculations)
mundane moral concerns about other people's suffering and so
on, many years ago I abandoned strict functionalism because
that recourse seemed to be the only "out".

I then claimed that although it looked like ordinary computation
(including conscious instances) from the outside, a Giant Lookup
Table (GLUT) would in fact not be conscious. The S-GLUT here
(for Simple GLUT) is assumed to take any state that it's currently
in and merely use that as an address of its next state. Example:
take a particular generation on Conway's Life Board (of a trillion
by trillion pixels) and instead of computing the next generation
by local rules (Rules of Life) use the whole 10^24 bits to look
up the next state.

But I was concerned that the noose of my argument wasn't
quite drawn tight enough; therefore, I made a slightly more
complex GLUT (this time with no "S-") that first took the
present state, used a perfect hash on it to produce (in Stuart
Armstrong's notation) f(s) where s is a state and f(s) is the
hash of that state (or bit string). Then *that* element would
be used as an address into the GLUT that would yield the
next state (e.g. the next generation).

It *was* probably a good idea to use f, because if you took
just a state of the Life Board (or of a human brain) and
simply encoded it by a raster scan or something into what
will be used as an address (for table lookup), then the
"connection" between two states is still relatively simple:
No, not quite as simple as Conway's Rules (or, for a human
brain, the laws of physics), but still, a fairly trivial algorithm
could unpack the string and then do local (simple) (and
perhaps *genuine*) computations on it to arrive at the
next state. (As Stuart would say, the KC of just going from
one state in the S-GLUT to the next would be low.)

By introducing the hash function f, I made sure that this
mapping would *not* be simple. An algorithm given f(s)
would have to (in order to *calculate* the next state)
first compute f^(-1) of f(s) and go from there. Thus my
GLUT, as it ended up, has this structure: at address
f(s) is the next state s'.

So, for example, a computronium machine that already had
this GLUT could hold a conversation with you as follows.
It's in state s1, and when you utter a syllable to it, it goes
into s2, which is (fundamentally) a function of s1 and your
input. Now, so far, that's how all of us are, and how any
machine is. But next, instead of "thinking" about your
syllable, I claim that as a very unauthentic form of computation
it merely does this: it adds your syllable to its present state
performs a complex (but perfect) hash on the result when
interpreted as a bit string, and using that hash as an address,
looks up its next state, which presumably includes a bit of
structure that is a little of the first formulation of something
it might be going to say back to you (for example).

And I argued at length, and still do, that surely this is not
conscious activity.

Stuart then created a couple of nice mathematical models
of this, about which it appears that exact results can be
proven, instead of relying on intuition as I had been doing.
I like his models very much.

He says this, taken verbatim from his earlier posts in
"The GLUT and Functionalism":

> S = a finite set of polynomials.

This is the analog of the state of someone's brain or
a generation in Conway's Life.

> G = a GLUT on S.

G takes a generation, state, (or actually, the hash of a generation
or state) and outputs "the next" state. I made it use *addresses*
in particular, but Stuart is abstracting away from that to explain
that G is actually a function. I don't think that the domain of the
function is S, however. The domain of the function G is the GLUT
itself; G takes entries of the GLUT to other entries. I hope that
all this explication is to Stuart's satisfaction.

> R = a rule that says that any polynomial of n-th degree will be
> mapped, under G, to a polynomial of (n-1)-th degree.

This is analogous to the rule in Conway's Life that would take a
generation to the next generation, or the laws of physics that would
take a human brain (or the present state of a conscious program)
to its next state.

> f = a hash function from S (to f(S))

> f(G) = the GLUT on f(S) equivalent to G on S.

Entries in this new GLUT-2 take elements GLUT-2 to other
elements of GLUT-2, which I now think is at odds with my
original conception, namely that in my GLUT, one could
visualize an address and the contents at that address,
respectively f(s) and s'. (So in my GLUT, the entries were
ordinary states, it's just that they were looked up by a very
peculiar process (the hash).) Perhaps it's really equivalent
to what Stuart as saying---but even if not, his model strikes
me, again, as very interesting and applicable.

> f(R) = the rule on f(S) equivalent to R on S.

While the rule R that takes, for example, s to s', is fairly simple
(e.g. the Rules of Life), this new rule f(R) seems to take hashes
to other hashes, though I may be confused.

Anyway, Stuart now writes

> 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
> another.

Well, that was without the use of the hash function. But now I see
where I wasn't understanding: any GLUT could be taken as a
function that took states of the GLUT to other states of it. Thanks
for explaining.

> 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
> GLUT).
>
> 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.

Yes, and pretty simple, too. You can locally examine (of course)
patches of a Life Board to get to the next generation, and still
rather trivially examine a simple raster scan or bit string (made
by taking the 10^12 x 10^12 Life Board and reading it out
one row at a time), and legitimately compute the next state.

> Now R is a rule, i.e. a restriction 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.

Well, I'm not really sure of that, or if it's profitable to speak that
way. G takes states of *this* GLUT to other states, and since
we haven't hashed anything yet, why emphasize that its KC
could be huge?

> Formulating the rule R itself is of trivial KC; [yes] 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).

Okay.

> 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.

What? How could that be? I would think that the connection
between f(P(n)) and f(P(n-1)) would be enormously more
complicated. (It's why I introduced the hash function f in the
first place.) Looks like we may have a slightly different idea
of what we're talking about.

Oh! Perhaps you simply mean that the literal table-lookup
connection between f(P(n)) to f(P(n-1)) is by definition
trivial, since it's just an assignment? (Sort of like the way
that the relation between an address and the contents at
that address is absurdly simple in my scheme.)

> But given an element p of f(S), knowing whether it is in f(P(n))
> is of very high KC: to do so,

Well, yes, it would be.

> we need to calculate f^{-1}(p), and the KC of f is maximal.

Yes.

> Thus the rule f(R) is of high KC, as it requires a lot of information
> to describe.
>
> With me so far?

Maybe! What does it look like to you? Is it safe to proceed? :-)

Lee



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