Re: terminal von Neumann

[Howard Pattee <***>]

John,
I realized that my von N references won?t help much if you can?t find them, so here are 
some edited notes I have used in my class on biological systems theory.

In order to understand the analogy to a universal constructor von Neumann made with a 
Universal Turing Machine you have to understand the essential duality (a virtual 
epistemic cut) between a DESCRIPTION and the THING  described, whether it is a formal or 
physical system.
One particular TM can compute only one particular function. In order for one and the same 
TM to be called Universal it must compute any function that any particular TM can 
compute. Turing saw that to do this one must be able to DESCRIBE any TM in a symbolic 
language that can be interpreted by the UTM such that it computes the function of the 
described TM. The crucial distinction, then, is between a TM and a DESCRIPTION of a TM. 
(Remember, we are still talking only about formal symbol systems, all on the right side 
of the modeling graph).

It was von Neumann?s recognition that the formal concept of any Turing machine was in a 
different causal category than real computation, and that any computational hardware 
itself must be constructed of matter and run by energy (placing it on the left side of 
the modeling graph). Now a hardware-only TM could be constructed realizing (only 
approximately, because it is finite and noisy) any particular TM, but it would be a 
special construction that would only compute one function. The distinction of a formal TM 
and the description of the TM suggested to von Neumann that for a hardware machine to be 
universal, that is, to compute more than one function, it would have to be controlled by 
a description of the function to be computed. Hence we now have our memory-stored 
programmed universal hardware computers. This implies a virtual epistemic cut, the 
hardware on the left and the program on the right with the relation between them called 
coding and decoding. (This situation Bob represents in his figure 3F.2 on p. 53 of LI.) 
So far, I can see no basic disagreements. Bob understood all this thoroughly.

Next we come to self-reproduction. Von Neumann states clearly that construction requires 
more than just the software driven hardware of a computer. Von Neumann titles this 
section, ?Broadening of the [UTM] program to deal with automata that produce automata.? 
He sees that ?Turing?s procedure is too narrow.? . . . This alone should make it clear 
that he is not ?confounding? computation with construction. Von Neumann continues:
?First of all, we have to draw up a complete list of elementary parts to be used. This 
must contain not only a complete enumeration but also a complete operational definition 
of each elementary part.? (General and logical theory of automata, in Cerebral Mechanisms 
of Behavior, Hixon Symposium, Vol. 5, No. 9, L. A. Jeffress, ed., Wiley, NY, 1951, pp. 
315-318)

Von Neumann has now distinguished three distinct categories, (1) formal UTMs, (2) 
memory-stored programmed computers, and (3) description-controlled constructors requiring 
a reservoir of parts. There is a long discussion of the so-called ?parts problem? because 
clearly the complexity of the parts will inversely affect the complexity of the 
description (instructions) for constructing the hardware. The material parts problem is 
clearly relevant only to construction. It has no parallel in formal simulation, formal 
computational, or any symbolic manipulations.

Here is the basic logic:
Von Neumann assumes an endless reservoir of parts that are needed to construct a physical 
device called X. We want X to replicate itself using the parts so that we end up with X 
and X?. Using the machine shop analogy, combined with the UTM analogy he assumes that 
given a suitable DESCRIPTION of X, called phi(X), there is a universal machine tool, A, 
that will build X from the parts. For this construction we write phi(X) > A = X. The 
constructor, A, is universal in the sense that A can construct X from a phi(X) where X is 
a member of some indefinitely large set of possible physical constructions that includes 
A as a member. This is the imperfect analog of the UTM that is universal in the sense 
that a UTM can compute the function of TM from a phi(TM) where TM is a member of an 
indefinitely large set of TMs.

Here the TM analogy breaks down because a formal description of a UTM when fed to itself 
does not define a function, whereas phi(A) when fed to A will construct another A. Here 
we must invoke the hardware machine shop analogy. The tools in a machine shop are 
versatile enough to construct a functional duplication of the machine shop from a 
sufficiently well-defined description of all the tools in the shop. This of course 
requires a set of stock parts that can be identified (coded) without given a complete 
description of the part. Von Neumann has a long discussion of the necessity of 
simplification of description of the parts (This corresponds to the simplification of 
amino acid descriptions by the genetic code).

Notice that the formal automaton resides entirely on the right side of the Hertz/Rosen 
modeling graph, while the machine shop tools are on the left side and their description 
is on the right side. It is actually the epistemic cut that prevents the possibility of 
logical antinomies. Contradiction is strictly a formal right-side concept. There are no 
contradictions in real systems. There are only incorrect descriptions on the right and 
impossible events on the left.

This is where von Neumann and Rosen saw a possible problem with purely formal 
self-replication. The UTM is itself a formal description of a set of all TMs that, if it 
is considered a member of this set, makes it a set that is a member of itself. This leads 
to the Richard antinomies. However, these antinomies can be avoided if recognized, and so 
they do not invalidate the formal computational argument, as many examples of 
self-replicating formal automata have demonstrated (e.g., Langton, Artificial Life, p. 
29. Also, Physica D 10(1-2), 135-144, 1984).

The final evolvable self-replicating unit consist of four hardware components and their 
descriptions: (1) the constructor, A, (2) the description copier, B, (3) the controller, 
C, and (4) the open-ended evolvable function, D. The process of replication requires A to 
construct all four hardware units from their descriptions. Then the hardware unit B 
copies their descriptions. The controller, C inserts the new descriptions in the new 
hardware constructed by A and takes care of reassembly. Whatever additional structures 
evolve as described by D will be automatically inherited. This can be abbreviated as 
follows:

phi(A + B + C + D) > (A + B + C + D) = phi(A + B + C + D) > (A + B + C + D)

This is the most basic description of how real cells replicate. The phi(A + B + C + D) is 
the genome, the A is the protein synthesis system (tRNA, synthetase enzymes, ribosome), 
the B are the DNA synthetases, the C are the mitotic structures (microtubules, membranes, 
etc.). The energy supply system is missing, but it can be added without changing the 
basic argument.

Few biologists even know about von Neumann argument, but physicists like Freeman Dyson 
are impressed at his prescience: "So far as we know, the basic design of every 
microorganism larger than a virus is precisely as von Neumann said it should be." . . 
."In evolving from simpler to more complex organisms you do not have to redesign the 
basic biochemical machinery as you go along. You only have to extend and modify the 
genetic instructions. Everything we have learned about evolution since 1948 (when vonN 
thought this up) tends to confirm that von Neumann was right." (from Disturbing the 
Universe)

I know this is a reductionist model, and I agree organisms need many other models, but 
this is one explanatory model for several interesting questions.

Howard