Von Neumann’s critique of automata theory and logic in computer science (1947)
1–10 of 35 posts
Re: Von Neumann’s critique of automata theory and logic in computer science (1947)
#2[deleted]
Re: Von Neumann’s critique of automata theory and logic in computer science (1947)
#3> In studying the functioning of automata, it is clearly necessary to pay attention to a circumstance which has never before made its appearance in formal logic. Throughout all modern logic, the only thing that is important is whether a result can be achieved in a finite number of elementary steps or not. The size of the number of steps which are required, on the other hand, is hardly ever a concern of formal logic. Any finite sequence of correct steps is, as a matter of principle, as good as any other. [...] Thus the logic of automata will differ from the present system of formal logic in two relevant respects. 1. The actual length of “chains of reasoning,” that is, of the chains of operations, will have to be considered.
Interestingly, according the Wikipedia [0], Gabriel Lamé published a running time analysis of Euclid's Algorithm [1] in 1844, more than a century before von Neumann suggested this.
[0] https://en.wikipedia.org/wiki/Computational_complexity_theor...
Re: Von Neumann’s critique of automata theory and logic in computer science (1947)
#4Controls engineer here.
I've often wondered what a theory of computation based in differential equations would look like. We desperately need one. Control theory gives us some tools, but not nearly powerful enough ones.
It's fairly clear by now that AI, at least as applied to domains immersed in the natural world, such as robotics and machine vision, is better thought of as analog in nature. Ten years ago I'd go to robotics conferences and it would not be unusual for me to be the only person in the room who knew that control theory was a thing. Now it's nearly taken over the field. But the kinds of developments we see in the field, both in terms of controls and in terms of machine learning, are essentially experimental in nature. We try some stuff, and see what works. Mathematical proofs, or even a mathematical understanding, of these algorithms comes later, if at all.
To this day we have intuition about why deep networks work, but backing that intuition up with rigorous mathematical analysis has been very challenging and is quite incomplete. But when it works, it works far better than ideas rooted in automata. It would be a tremendous benefit to the field if we could somehow merge the practical power of differential equations and function approximators with the theoretical power of the theory of computation.
Re: Von Neumann’s critique of automata theory and logic in computer science (1947)
#5Controls engineer here. I've often wondered what a theory of computation based in differential equations would look like. We desperately need one. Control theory gives us some tools, but not nearly powerful enough ones. It's fairly clear by now that AI, at least as applied to domains immersed in the natural world, such as robotics and machine vision, is better thought of as analog in nature. Ten years ago I'd go to r…
> It would be a tremendous benefit to the field if we could somehow merge the practical power of differential equations and function approximators with the theoretical power of the theory of computation.
If you consider Leslie Lamport's TLA+ [0] bringing logic specifications tied to software, it comes close to what you are looking for IMHO. Code the differential equations in your code but use TLA+ for the mathematics and theory of computation.
[0] http://lamport.azurewebsites.net/tla/high-level-view.html
Re: Von Neumann’s critique of automata theory and logic in computer science (1947)
#6"formal logic ... deals with rigid, all-or-none concepts"
Von Neumann only had knowledge of classical logic, so he was not aware of fuzzy logic, logics that deal with infinite truth values, and other non-binary logics.
By recognizing the above named inadequacy in the formal logic that he knew, von Neumann was unwittingly standing on the threshold of a new field. If only he had asked the right question (ie. what could a non-binary logic look like?), a first rate mind like his surely could have made some significant progress.
Re: Von Neumann’s critique of automata theory and logic in computer science (1947)
#7"formal logic ... deals with rigid, all-or-none concepts" Von Neumann only had knowledge of classical logic, so he was not aware of fuzzy logic, logics that deal with infinite truth values, and other non-binary logics. By recognizing the above named inadequacy in the formal logic that he knew, von Neumann was unwittingly standing on the threshold of a new field. If only he had asked the right question (ie. what could…
[deleted]
Re: Von Neumann’s critique of automata theory and logic in computer science (1947)
#8"formal logic ... deals with rigid, all-or-none concepts" Von Neumann only had knowledge of classical logic, so he was not aware of fuzzy logic, logics that deal with infinite truth values, and other non-binary logics. By recognizing the above named inadequacy in the formal logic that he knew, von Neumann was unwittingly standing on the threshold of a new field. If only he had asked the right question (ie. what could…
Von Neumann was thoroughly familiar with non-classical logic. He himself came up with several variants (including quantum logic) in the 1930s.
Re: Von Neumann’s critique of automata theory and logic in computer science (1947)
#9> In studying the functioning of automata, it is clearly necessary to pay attention to a circumstance which has never before made its appearance in formal logic. Throughout all modern logic, the only thing that is important is whether a result can be achieved in a finite number of elementary steps or not. The size of the number of steps which are required, on the other hand, is hardly ever a concern of formal logic.…
[deleted]
Re: Von Neumann’s critique of automata theory and logic in computer science (1947)
#10Related:
* Kurt Gödel's Letter to John von Neumann (1956)
https://news.ycombinator.com/item?id=19281633
Gödel was asking John von Neumann the number of steps for solving the Entscheidungsproblem. I asked on HN for its background, and I was told it was one of the earliest discussions of computational complexity theory, unfortunately John von Neumann did not have a chance to reply.
Thanks for posting it, now I see the bigger picture: even without seeing Gödel's letter, John von Neumann had already grasped the idea of computational complexity independently around the same time.