As an answer to the question "are there finite mathematical descriptions that are not effective" posed by Hilbert, Turing provided the halting function as being not effectively computable despite being finitely expressible. This he established by devising the mechanism of Turing Machine, an abstract machine that captured the logic of thought (see Ref 1). In similar lines, von Neumann tried to capture the logic of life through the mechanism of computation, one of his attempts resulting in cellular automata and the self-reproduction theories (see Ref 2).
The primary question is: Self-reference posed a limitation on the logic of thought – can self-reproduction place any such limitation on the logic of life?
Interesting point to be noted here is that researchers study both self-reference and self-reproduction as being applicable to both human-beings as well the machines (see: NASA's Advanced Automation for Space Missions). However, oftentimes it appears that only machines suffer from the self-reference problem while human-beings get along with it fine. Then what about self-reproduction?
In a strict object-oriented sense the term self-reproduction is paradoxical. There is nothing like an object producing "itself". Nevertheless the concept of self-reproduction, at least from the experience of human-beings throughout centuries, is quite clear enough to mean it as the production of similar entity as opposed to "same" entity. This is in contrast to the concept of self-reference, where an object strictly refers to the "same" entity and not a similar entity. Further, if one goes slightly deep in understanding these terms, it could even appear that the whole concept of self-reference is paradoxical too. Details are as below.
A self-reference essentially is a reference (or addressing) mechanism. For it to work, the basic requirement is that one should be able to specify addresses for individual objects. In doing so, any addressing mechanism one thus chooses to use must be able identify each and every object uniquely. One can use any indexing scheme for this purpose (such as those described at Sequence Indexing). And Turing as well Gödel have used what is known as Gödel numbering mechanism:
The numbering does not take the knowledge of the object into account while computing its number. That is, the consideration of whether or not an object knows its number is not taken into account while computing its number. This is because, if one has to take the objects' knowledge into account then,
- Object would change its state from before the numbering to after the numbering (as the object has gained additional knowledge about its number) and thus is not the same object any more. In such scheme there exists no way of numbering the objects as each and every numbering keeps changing the objects' knowledge.
On the other hand, if object does not change the state, then there is no way the object would know the number (or the address) it was given in the process of numbering and thus can never tell if any given number is its own or not. Thus in that case there should exist an external entity that once given an object can return its number and vice-versa. However, there are two things to be considered in this scheme. How would the external entity actually supply the object once given the id? Would it make an exact replica and supply it or would it supply the actual object itself? When an object tries to retrieve the object referred by its own number (as self-reference),
- If external entity returns a replica, then it is no more self-reference. (Working on a replica is not the same as working on the object.)
- If external entity returns the object itself, then how can the object get "itself"? (once the external entity grabs the object based on its number, then there would be no one to give it to (as the object is already being held by the external entity), and once the external entity relieves the object it is holding then there would nothing to give to the object (as the external entity holds nothing).
- The other possibility is where every object is modified to include the procedures of computing the numbers from the objects and vice-versa in them and make the objects use those procedures whenever they needed to compute their own number from their own state or get any other object from any given number. Thus, each object is portrayed as having two parts, one containing all of its state information that never changes or gets affected by the second part, which contains the procedures to operate on the contents of the first part. This is strikingly similar to what today's computing programs have in them – the data and executable portions, and even what the human-beings have with them – body and mind.
Could it be that the concept of self-reference vs. self-replication finally boils down to the mind-body problem?
- Alan M Turing, On computable numbers, with an application to the entscheidungs problem, Proceedings of the London Mathematical Society 43 (1936), 2
- Neumann, J. V. 1966 Theory of Self-Reproducing Automata. University of Illinois Press
- Gopalakrishna Palem, Efficient Sequence Indexing for Game Development, Game Programming Gems 6, 2006.