Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Von Neumann’s critique of automata theory and logic in computer science (1947)

yodaiken.com

Post reply on HN
Print view View original

11–20 of 35 posts

Re: Von Neumann’s critique of automata theory and logic in computer science (1947)

#11

Post by projectileboy »

GlenTheMachine wrote: post #4

Controls 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…

This is slightly tangential, but if you haven’t already seen it, you should check out Danny Hillis’ story of Richard Feynman working at Thinking Machines. He solved how big the buffers needed to be for the communications between processors by modeling the bit streams with partial differential equations. http://longnow.org/essays/richard-feynman-connection-machine...

Re: Von Neumann’s critique of automata theory and logic in computer science (1947)

#12

Post by currymj »

GlenTheMachine wrote: post #4

Controls 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…

Lenore Blum has worked on some things in this direction.

http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf

I think most computer scientists have a natural and justified distrust of the real numbers, though, because when you get down to it they are too bizarre and impossible to actually be real. (i.e. the set of computable reals has measure 0, see Chaitin).

https://arxiv.org/pdf/math/0411418.pdf

Re: Von Neumann’s critique of automata theory and logic in computer science (1947)

#13

Post by jhanschoo »

Today, there are at least two fields that address just these issues: the field of computational complexity investigates just how many operations are required depending on the problem.

I'm not too familiar, but I think control theory addresses the issue that requires accounting for the possibility for error.

Ad for the other field, when von Neumann mentions analytical tools, he is actually thinking of topological tools. To that end, Type theory investigates formal logic with much inspiration from topological tools.

Re: Von Neumann’s critique of automata theory and logic in computer science (1947)

#14

Post by blt »

Prescient. Nowadays, most computer scientists don't explicitly worry about hardware failures, but we still love randomized algorithms.

Often it's easy to prove that a randomized algorithm has a desirable property with probability 1 asymptotically, or with high probability in finite time. In contrast, it's often hard to prove the analogous desirable property always holds for a deterministic algorithm. In other words, we use a trick to make a combinatoric problem more like an analysis problem, because analysis problems are easier to handle -- exactly what Von Neumann was writing about!

Turns out, the power of analytical methods was its own motivation, and we didn't need unreliable hardware to push us in that direction.

Re: Von Neumann’s critique of automata theory and logic in computer science (1947)

#15

Post by mav3rick »

projectileboy wrote: post #11
GlenTheMachine wrote: post #4

Controls 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…

This is slightly tangential, but if you haven’t already seen it, you should check out Danny Hillis’ story of Richard Feynman working at Thinking Machines. He solved how big the buffers needed to be for the communications between processors by modeling the bit streams with partial differential equations. http://longnow.org/essays/richard-feynman-connection-machine...

Fantastic read

Re: Von Neumann’s critique of automata theory and logic in computer science (1947)

#17

Post by garganzol »

GlenTheMachine wrote: post #4

Controls 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…

That is a deep philosophical quest and I find myself attached to it for my whole life. Now I would share some recent observations.

A LISP program with one entry function without side effects is the closest bridge between the conventional computation and conventional math.

If such a program would consist from only a well known set of math functions (sin, cos etc) then it would be immediately ready for typical math instruments like differentiation, integration etc. Let's call such malleable functions as ones to be in _analytical_ form.

Now add some Boolean logic. It's binary so you cannot apply the "analog" analytical math rules. But there is a trick. It is called Rvachev functions. They allow to represent Boolean functions in malleable analytical form.

Having math and logic is very close to generic computation, but not enough. You also need a notion of conditional jump (sometimes called goto or branch) for it to be a Turing-complete.

But functional languages like LISP provide a treasure trove here too. They often use jumps/gotos and functional recursion interchangeably. So, if a program is represented in malleable analytical form and uses recursion for control flow without side effects... it is not different from your typical math formula. So you can differentiate, integrate and do whatever a conventional math can do. Really intriguing.

>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.

There were folks who translated trained networks to automata in order to squeeze them into smaller microcontrollers/FPGAs. Quite a result if you ask me. It shows that the trained AI and automata are interchangeable forms of the very same thing - computation.

Re: Von Neumann’s critique of automata theory and logic in computer science (1947)

#18

Post by YeGoblynQueenne »

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 computer science (1947)

#19

Post by garganzol »

currymj wrote: post #12
GlenTheMachine wrote: post #4

Controls 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…

Lenore Blum has worked on some things in this direction. http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf I think most computer scientists have a natural and justified distrust of the real numbers, though, because when you get down to it they are too bizarre and impossible to actually be real. (i.e. the set of computable reals has measure 0, see Chaitin). https://arxiv.org/pdf/math/0411418.pdf

I had that distrust of the real numbers too. It looks it's pretty common among CS folks.

However, one of my professors once said: "There is a beauty in real numbers. While they cannot be as precise as decimals, they allow to see the nature of things by exploring and discovering the laws of the universe."

Time passed and I cannot agree more. It's indeed a proverbial quote that should be given to all CS students.

Re: Von Neumann’s critique of automata theory and logic in computer science (1947)

#20

Post by rini17 »

GlenTheMachine wrote: post #4

Controls 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 seems to me like I am missing something: In most practical cases, the differential equations are solved numerically anyway. Why add the extra step?
Post reply on HN