On Wed, 2005-05-11 at 11:46, "Hal Finney" wrote:
> Eric Cavalcanti writes:
> > Let's define a turing machine M with a set of internal states Q,
> > an initial state s, a binary alphabet G={0,1}. The transition
> > function is f: Q X G -> Q X G X {L,R} , i.e., the function
> > determines from the internal state and the symbol at the pointer
> > which symbol to write and which direction (left or right) to
> > move. 
> >
> > Write a program in M that calculates the evolution of a harmonic
> > oscillator (HO). The solutions are to be N pairs of position and
> > momentum of a HO, with time step T and d decimal digits. Let this
> > set of pairs be P.
> >
> > The program will eventually halt and the tape will display a string
> > S.
> > ...
> > Is there some "harmonic oscillatorness" in S?
> 
> Yes, potentially there is.  The first thing you need to do is to
> define a harmonic oscillator.  Obviously you can't ask whether there
> is X-ness in something if you don't have a definition of X.

Sure.

> So let us write a definition of a harmonic oscillator.  Express it as a
> program which, when given some input that claims to describe a harmonic
> oscillator, returns true if it is one, and false if it is not.  This
> input can be required to be in some canonical form.

Agreed.

For example, I can write a program for which the input is a sequence
of N k-digit numbers, where each k-digit number encodes a pair (x,p)
in a given way. And then I can go and write a program to check if these
numbers behave closely like a harmonic oscillator.

> Now, if string S truly contains a harmonic oscillator, we should be
> able to write a simple program which translates S into the form needed
> for input to our test program, and which will then cause the test
> program to return true.

This is the hard part. If we don't know how the pairs are coded in the
string, which ultimately depends on the programmer's design, how can we
do that in general? And in the end that just amounts to finding
the mapping A that I defined before, the existence of which seems to be
utterly dependent on a programmer/cracker.

Further, given some complex enough string, you could always find SOME
mapping from that string into the set P of coordinates of a harmonic
oscillator, which uses SOME code. Right? I guess that's along the lines
of what you say below:

> The key is that the translation program must be simple.  The simpler it
> is, the greater the degree to which we can say that S contains a harmonic
> oscillator.  The more complex it is, then the harmonic oscillator is as
> much in the mapping as in S.

But is there some natural objective way of making this translation? Can
we say that these translation programs exist out there independent of
people to make them and that they make some objective sense out of
dead strings in Platonia?

Further, these mappings are completely arbitrary, since they not only
depend on the coding in the input, which isn't known a-priori, but on
the design of the program that's testing the "harmonic oscilatorness"
of the string. It could happen that by accident, a string which is
the output of a program that simulates a dancing Santa could pass the
"harmonic oscillatorness" test.

> This argument gains strength when we are dealing with an object more
> complex than a harmonic oscillator.  If the object we are testing for
> is so complex that it takes billions of bits to specify, then as long
> as the mapping program is substantially smaller than that size, we have
> an excellent reason to believe that the object is really in S.

Hmm... I vaguely see your point but remain unconvinced that there is
something objective about the mapping.

> Now, I have cheated in one regard.  I don't know of an objective way of
> judging whether the mapping program is simple.  There are some results
> in algorithmic information theory which go part way in this direction,
> but there seem to be loopholes that are hard to avoid.  So things are not
> quite as simple as I have said, but I think the thrust of the argument
> shows the direction to pursue.

I don't have as much problem with the simplicity of the mapping as
with the objective existence of it. I could provisionally accept that
there is some objective meaning to simplicity but I wouldn't be
yet satisfied.

Eric.

Reply via email to