Yes, I think that at least some of what Von Neumann is calling for is complexity theory. It's easy to forget how recent complexity theory is. While Hartmanis a

Yes, I think that at least some of what Von Neumann is calling for is complexity theory. It's easy to forget how recent complexity theory is. While Hartmanis and Stearns laid the foundations in 1965, its first concrete result came only in '71 (Cook) and '72 (Karp), and it took much longer for more results, and, more importantly, their meaning, to sink in (at least until the '80s if not later) among computer scientists who are not themselves computational complexity researchers. In fact, some of the most basic results complexity researchers rely on are from the mid 80s (circuit complexity), which makes complexity theory one of the youngest fields in computer science. It is about half the age of neural networks, and even younger compared to programming language theory. Some famous assertions/hypotheses/aspirational programs in computer science, including by people like Dijkstra, Tony Hoare and Robin Milner, predate complexity theory, and should be seen in a different light because of that. And because it is so young compared to other branches of computer science, it is sometimes ignored by researchers working in older disciplines, if only because their own basic results predate complexity theory.