Today, I was reading Sipser’s Theory of Computation and in chapter 6 it said:
For statement 3 (Machines cannot self-reproduce) we make the following argument that machines cannot self-reproduce. Consider a machine that constructs other machines, such as an automated factory that produces cars. Raw materials go in at one end, the manufacturing robots follow a set of instructions, and the completed vehicles come out at the other end.
We claim that the factory must be more complex than the cars produced, in the sense that designing the factory would be more difficult that designing a car. This claim must be true because the factory itself has the car’s design within it, in addition to the design of all the manufacturing robots. The same reasoning applies to any machine A that constructs machine B. But a machine cannot be more complex than itself. Consequently, no machine can construct itself, and thus self-reproduction is impossible.
How can we resolve this paradox? The answer is simple: Statement 3 is incorrect. Making machine that reproduce themselves is possible. The recursion theorem demonstrates how.
Sipser then goes on to talk about Turing Machines which behave as a quine.
This could be a resolution to a burning question that I have: Is it possible to have an Algebra of Algorithms?
It would be very useful if we could. I imagine that such a structure would be akin to the combining forms of Backus’ Functional Programming. But on the other hand, algorithms are more complex than an algebra, and their internal relations might be too complex to encode in an algebra. Intuitively you should not be able to talk about a complex thing in a language simpler than the object under discussion, yet the very existence of a quine suggests otherwise. I am very interested in resolving this issue, as it has deep applications to my primary area of study: The relationship between what we think (algorithms) and what we say (programs).
In order to resolve this issue I should probably ask: Does there exist an encoding of Turing Machines such that a machine computationally weaker than a Turing Machine (ex: Stack Machine, or Finite State Machine) can determine whether or not a string is a valid description of a Turing Machine?
Aside: this whole train of thought provides a nice rebuttal to anyone (religious-types) that prefer to maintain that a Finite beings can’t understand The Infinite. Honestly, humans made up the concept of the finite and the infinite, but most people haven’t gotten past the thinking prior to 1890‘s, and are instead stuck in the christian apologetics of the dark ages, refusing to accept modern logic’s discoveries about the infinite.