# Decoding a Remark of Gödel on Complexity Theory

In Gödel's Collected Works (Vol 2), there is a discussion of von Neumann which was brought about by a query, made to Gödel, concerning the existence of a Turing machine which is so complex that its total halting behavior is "asymptotically more complicated to describe than the machine itself".

To this, Gödel replied:

"What von Neumann had in mind is probably best understood through the notion of a Universal Turing machine $U$. There, it might be said that a complete description of its behavior is infinite because, in view of the non-existence of a decision procedure predicting $U$'s behavior, any $\textit{complete}$ description of $U$ could only be given by an enumeration of all instances. Thus, the Universal machine, where the ratio of the two complexities is infinite, might then be considered as a limiting case for all Turing machines." [italics mine].

What I am puzzled about is the precise statement of what Gödel asserts as "the ratio of the two complexities" which tends to infinity. From the context, I gather that this is the ratio between (1) the procedure which supplies the "complete enumeration of $U$" and (2) $U$ itself with respect to its termination. Clearly, he considers this as a type of worst-case analysis for $U$, but unfortunately I cannot gather a sharp statement about the procedure which supplies the complete enumeration so that I could prove that this is indeed a worst-case analysis or simply something else that I have missed.

Is there a proof related to this fact?