In the late 1940s John von Neumann began to work on what he intended as a comprehensive “theory of [complex] automata.” He started to develop a book length manuscript on the subject in 1952. However, he put it aside in 1953, apparently due to pressure of other work. Due to his tragically early death in 1957, he was never to return to it. The draft manuscript was eventually edited, and combined for publication with some related lecture transcripts, by Burks in 1966. It is clear from the time and effort that von Neumann invested in it that he considered this to be a very significant and substantial piece of work. However, subsequent commentators (beginning even with Burks) have found it surprisingly difficult to articulate this substance. Indeed, it has since been suggested that von Neumann's results in this area either are trivial, or, at the very least, could have been achieved by much simpler means. It is an enigma. In this paper I review the history of this debate (briefly) and then present my own attempt at resolving the issue by focusing on an analysis of von Neumann's problem situation. I claim that this reveals the true depth of von Neumann's achievement and influence on the subsequent development of this field, and further that it generates a whole family of new consequent problems, which can still serve to inform—if not actually define—the field of artificial life for many years to come.