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

The theory of computation is not based on anything; it is fundamental in the sense that it exposes laws of nature (it is heavily based on physical limitations) independent of the means of talking about them. In a very strong sense it is more fundamental than mathematics itself as it is concerned with how hard it is to obtain the answer to a mathematical question without regard to the process of obtaining it. Different representations may, of course, assist us in proving certain theorems in the theory of computation or other areas of computer science.

On the other hand, systems based on digital logic are very "discontinuous". A small changes in an input can result in the system behaving vastly different. A single-bit error in a computer program can result in an if-then-else switching from the true branch to the false branch, and thereby running an entirely different piece of code. So your computer is a single bit flip away from fintech entrepreneurs using your entire bank account to rent AWS time to mine Bitcoin.

In general, we are drawn to discrete logic because it's easy to write programs to do different things based on different inputs. However, von Neumann was worried about this, because no machine works perfectly -- every computer runs with a certain probability of error, and computers run fast enough that even a low probability of error can compounds very quickly. And if a single small error can result in radically different results, how can you trust the result of a computer program?

In this note, written in 1947, he expressed the hope that if you could make computers behave continuously, you could not worry about small errors, because they would only have a small impact on the result.

However, a few years later von Neumann ALSO invented the alternative, modern way of handling these issues! In his 1956 paper _The Synthesis of Reliable Organisms from Unreliable Parts_, he proved that it was possible to use redundancy in a way to drive the error probability arbitrarily low, enough that you COULD trust the output of a computation.

Solving DE in computation is an interesting point to make tho. I've seen analysis style arguments, like real analysis or calculus, in symbolic languages like lisp.

Actually, there's a really interesting set of papers very much related to this topic. Link below.

http://strictlypositive.org/calculus/

You're right that you can't have a theory without some language to talk about it (and it also requires people to come up with it, so is psychology more fundamental than physics?), but the theory of computation is about the laws that govern the power of mathematics. I.e. mathematics (and the universe) was constrained by computation long before anyone knew that. On the other hand, Turing was very careful not to rely on any mathematical and even logical results in his 1936 paper, not even on the principle of explosion (which is used in modern formulations of the halting theorem), precisely because he knew he wanted to get at the fundamental limitations of the very process of deduction itself (he does say that the theorem can be proven using the principle of explosion, but that would be "unsatisfying"). Turing showed that if a premise can be written as some string of symbols and so can the conclusion, then, due to constraints on the mind and body of the mathematician writing them, the process of deduction is subject to the laws of computation. This applies without any need to describe what the symbols represent, if they represent anything at all.

While the theory of computation does use concepts such as functions or sets, it knowingly treats them as higher level ideas than computation. I.e. a number or a set or a function is a name given by humans to something that can be computed or an abstraction of such a thing (so we can talk of non-computable things).

And if you want to include TOC as part of mathematics (some do, some don't), then it is its most fundamental part, more fundamental than formal logic (some people include that in mathematics, but most don't), which is subject to the laws of computation but not vice-versa.