News for hackers. Stuff that matters.
Re:Von Neumann’s critique of automata theory and logic in co... by YeGoblynQueenne on Sunday May 26, 2019 @04:32AM (#20013813)
If I understand this correctly, Von Neumann is saying that, in the real world, computation will have to be efficient and robust, and so techniques will have to be developed to ensure their efficiency and robustness and that such techniques will necessarily have to be continuous in nature - because combinatorics is too hard to be used for the job.

It's important to remember that this was written in 1947. So, a year before Shannon's paper on information theory and several years before the beginnings of complexity theory [1]. These are both discrete forms of analysis and they both go a long way towards addressing Von Neumann's 1947 concerns.

I don't know to what extent Von Neumann considered his 1947 criticism addressed by the subsequent advances. I'm going to go out on a limb though and say the he would probably have found at least some satisfaction in them.

______________

[1] Shannon's A Mathematical Theory of Communication paper was published in 1948. Wikipedia tells me that the foundations of complexity theory were laid down in 1965 in a paper titled On the Computational Complexity of Algorithms, by Juris Hartmanis and Richard E. Stearns.

https://en.wikipedia.org/wiki/Computational_complexity_theor...

Re:Von Neumann’s critique of automata theory and logic in co... by pron on Sunday May 26, 2019 @06:57AM (#20014276)
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.