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?


I just read that as saying U's description is finite in size, but describing U's behavior across all inputs needs an infinite description. There is no finite algorithm to say which inputs halt.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.