RE: Implementation

From: Marchal <>
Date: Wed Aug 4 09:38:56 1999

Hal Finney wrote:

>To follow up on Bruno's comment, can we use a HLUT type structure to
>implement something equivalent to a universal Turing machine?
>The TM can be thought of as implementing an algorithm, mapping from an
>input tape to an output tape. We can do the same thing with an HLUT,
>using the contents of the input tape as the index to look up an entry
>in the "humongous" table. The data at that entry in the table is then
>put out as the contents of the output tape.
>The resulting system, let's call it HLUT-TM, if considered as a "black
>box", has the same I/O behavior as the TM. We could even include a
>time-delay value in the HLUT if we wanted the HLUT machine to take the
>same amount of time as the TM.

It is not possible, strictly speaking, to build a HLUT which could
compute a simple function like factorial(x) or any growing functions
defined on N (the set of natural numbers), etc. Clearly the LUT must
be infinite (omega-infinite).

In denotational semantics (an approach in the mathematics of
of programs) such a LUT is a set representation of the semantics of the
and I am used to do that too. The meaning of <code of a factorial
algorithm> =
the infinite set {(0 1)(1 1)(2 2)(3 6)(4 24)(5 120) ...}.

So, an omega sized LUT (omegaLUT) can easily 'simulate' a UTM and any TMs.
An omega sized LUT can be seen as a semantics of a syntactical, formal,
terrestrial TM. UD* can be defined as the omegaLUT of an UTM, for exemple.
Now, someone could argue that in my lifetime I would not be able to
a universal machine with a 'n-truncated' LUT.
Well, perhaps, but I don't know if my lifetime is finite. So ...

In fact the only difference between a UTM and any of her 'n-truncated'
approximations is that for an arbitrarily vast (but finite) portion of
TIME/SPACE they are equivalent, but for the rest of the time the UTM is
correct and the n-truncated' LUT is false. A computer scientist would say
that all the n-truncated LUT are a.e.false (*almost everywhere* false).

Put in another way, the UTMs are counterfactually correct and the
n-truncated' LUTs can be said n-counterfactually incorrect a.e.

The n-truncated' LUT doesn't succeed in the limit.
If you remember the PE-omega experience you know that with comp the
of my 'next' personal experience is defined in the limit too, thanks to
mechanist non-locality of consciousness and the mechanist indeterminism.

I have no Zombie friends. If a superneuroscientist told me that my friend
X hasn't
a normal (= counterfactual implementation of) brain but a HLUT. The only
question for me is how big is H, for this will give me the amount of
I will be able to share with him.
How long will I remain in touch with him, for exemple.

'Him' and her consciousness is linked to an abstract and/or immaterial
story, not
to a 'physical' or just 'concrete' computation.

>[Hal] [...]
>You could imagine doing this on larger and larger scales. At the
>smallest level you have a simple optimization that wouldn't seem to
>have any significant effects, but at the highest level you essentially
>have a HLUT. If you want to say that the original system was conscious
>(say, the CA is running a TM which is running a conscious program),
>but you don't want to say that the HLUT is conscious, you have to say
>something about at what point consciousness would go away. You also
>have to say whether consciousness would go away gradually or suddenly
>as larger volumes of the CA are swept into the local lookup tables.

I agree. I take that for a difficult problem for those who still want to
consciousness'flux with physical phenomenon.
I just do not attribute consciousness to an implementation, but to a
...whatever implements that person. If at some stage her behavior is
'buggy', I
will be disappointed whatever causes the buggy behavior (n-truncatedness
n little, 'lost of the Klaras in a new situation' or cerebral tumor,
Alzeimer, etc.).


PS And all this does not solve the mind-body problem for now we must
and isolate the measure on the computation, and extract the laws of
physics from
there. This last fact provides hints and it is not forbidden to look at
current physics, of course.
Received on Wed Aug 04 1999 - 09:38:56 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:06 PST