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