On the Limits of Automated Discovery

As noted, I’m working on a physics engine that will allow for the automated discovery of physical laws, just like machine learning is used in many other areas of study, allowing for the automated discovery of useful relationships between observables. While running this morning, I stumbled upon what I thought to be an interesting, related question:

Can a UTM design another machine that is more powerful than a UTM?

This is distinct from a UTM writing a program that is more powerful than a UTM, which is on its face nonsense, since the resultant program will run on a UTM in the first instance. This is instead, the question of whether or not a Turing Equivalent machine can design another machine altogether, that is superior to a UTM?

Let $U$ be some UTM, and assume that a program $f$ causes $U$ to discover the design of some other machine $X$, that is superior to a UTM. It must be the case that the output $Z = U(f)$, is some representation of the machine $X$. If $Z$ is a complete and accurate representation of the machine $X$, then it must be possible to physically build $X$, given the representation $Z$. In plain English, if the computer really discovers another machine, then it must be the case that the computer can tell you how to build the new machine.

As a result, there is some mechanical process that produces the actual machine $X$, given the representation $Z$. This implies that a sufficiently dexterous machine can actually construct $X$ given $Z$, without human assistance. This in turn implies that the construction of the new machine $X$ is a mechanical process, which, according to the Church-Turing Thesis, can be simulated by a UTM.

But that’s not the correct question:

The correct question is whether the behavior of $X$ can be put into a 1-to-1 correspondence with the behavior of a UTM. This turns on the rules of physics, not computer theory. That is, we can’t know the behavior of $X$, without first knowing all of the physics relevant to the behavior of $X$. This doesn’t imply that it is possible for a UTM to design a machine that is superior to a UTM, but rather, that computer theory alone can’t provide an answer to this question.

Advertisement