Re: where is the harmonic oscillatorness?

From: Hal Finney <hal.domain.name.hidden>
Date: Tue, 10 May 2005 18:46:30 -0700 (PDT)

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.

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.

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.

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.

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.

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.

Hal Finney
Received on Tue May 10 2005 - 18:46:30 PDT