The cover of Avi Wigderson’s book “Mathematics and computation” as was first exposed to the public in Avi’s Knuth Prize videotaped lecture. (I had trouble with 3 of the words: What is EGDE L WONK 0? what is GCAAG?GTAACTC ? TACGTTC ? I only figured out the first one.)

Avi Wigderson’s book “Mathematics and computation, a theory revolutionizing technology and science” is about to be published by Princeton University Press. The link is to a free copy of the book which will always be available on Avi’s homepage. (See also this re-blogged post here of Boaz Barak.)

One main theme of the book is the rich connection between the theory of computing and other areas (in fact, most areas) of mathematics. See also this self contained survey (based on Chapter 13 of the book) by Avi Interactions of Computational Complexity Theory and Mathematics, which in 27 pages overviews relations to number theory, Geometry, Operator Theory, Metric Geometry, Group Theory, Statistical Physics, Analysis and Probability, Lattice Theory and Invariant Theory. Of course, over the last four decades, Avi himself has been among the main heroes in finding many paths between mathematics and the theory of computing.

Another theme of the book and of several talks by Avi is that the theory of computing has revolutionary connections with many fields of science and technology. Again, this theme is present in the entire book and is emphasized in Chapter 20, which also appeared as a self contained paper “On the nature of the Theory of Computation (ToC).” Let me quote one sentence from Avi’s book that I propose for discussion. (For the complete quote see the end of the post.)

## The intrinsic study of computation transcends human-made artifacts, and its expanding connections and interactions with all sciences, integrating computational modeling, algorithms, and complexity into theories of nature and society, marks a new scientific revolution!

Of course, similar ideas were also expressed by several other prominent scientists, and let me mention Bernard Chazelle’s essay: The Algorithm: Idiom of Modern Science. (Feel free to give further examples and links in the comment section.)

### Let’s discuss: Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!

I propose to discuss in the comment section the idea that the theory of computing offers a scientific revolution. Very nice cases to examine are the computational study of randomness and connections to statistics, connections with economy and connections with biology. Comments on the relations between the theory of computation and other areas of mathematics are also very welcome.

Avi’s concluding slide compared these three great theories of human understanding.

(Previous attempts of open discussions were made in the following posts on this blog: 10 Milestones in the History of Mathematics according to Nati and Me; Why is mathematics possible? (and a follow up post); When it rains it pours; Is it Legitimate/Ethical for Google to close Google+?; An Open Discussion and Polls: Around Roth’s Theorem; Is Mathematics a Science?)

Avi promotes the idea of the central place of the theory of computing in his talks and writings

And at the same time he is also humorously skeptical about it. (And mainly emphasizes that his far reaching claim requires careful discussion and ample evidence.)

### The full quote of Avi:

The Theory of Computation is as revolutionary, fundamental and beautiful as major theories of mathematics, physics, biology, economics… that are regularly hailed as such. Its impact has been similarly staggering. The mysteries still baffling ToC are as challenging as those left open in other fields. And quite uniquely, the theory of computation is central to most other sciences. In creating the theoretical foundations of computing systems ToC has already played, and continues to play a major part in one of the greatest scientific and technological revolutions in human history. But the intrinsic study of computation transcends man-made artifacts. ToC has already established itself as an important mathematical discipline, with growing connections to nearly all mathematical areas. And its expanding connections and interactions with all sciences, naturally integrating computational modeling, algorithms and complexity into theories of nature and society, marks the beginning of another scientific revolution!

### More related material:

- Avi’s talk Scientific revolutions, ToC and PCP at the Tel Aviv PCP meeting and an interview of Avi by Alon Rosen.
- A talk by Avi on the Stepanov method
- The recent works on polytopes arising from moment maps and related optimization problems and algorithmic aspects. Avi’s Knuth prize videotaped lecture; Avi’s lecture Complexity, Optimization and Math (or, Can we prove that P != NP by gradient descent?) in the recent conference honoring Bill Cook. (I plan to come back to this fascinating topic.)
- An essay by Oded Goldreich and Avi Wigderson (essentially from 1996) “The theory of computing – a scientific perspective.”

The volume of comments in the first decade of this blog was modest. I recently read, however, wordpress’s advice on how to reply to blog comments like a pro.

And finally, EGDE L WONK 0 is 0-knowledge.

“GCAAG?GTAACTC ? TACGTTC” I imagine they are DNA sequences.

I’m looking forward to reading this book.

Thank you, Steve. I didn’t think at all in this direction.

A,G,C,T are the common shorthand for the for bases that make up DNA, so words in those letters are DNA sequences.

Thanks, Lior. Luca Trevisan made the following suggestion over FB: The automaton shown on the right reads a 0/1 string and outputs a string of As, Gs, Cs and Ts, so the circled string should be the output of the automaton given the 0/1 string at the top (see also the arrows marked “read” and “write”), although, even taking “?” to be a wildcard symbol, they don’t seem to match

Surprisingly, Lior, I used similar AGCT DNA sequence for a recent drawing in my paper and still it did not occur to me that this is the explanation here 🙂

0 (ZERO) KNOWLEDGE

While both the connection between the theory of computing and other areas of mathematics and the connection between insights and methods from the theory of computing and other sciences are fascinating, it does not seem that we are heading for a large scale discussion over here. Anyway, one point I thought about is that economics might be a good example.

One interesting analogy to to ToC is theoretical economics and one can examine the role of theoretical economics in social sciences; the connections between theoretical economics to other areas of economics and to the economic reality. Of course the connections of ToC with economics that Avi discusses are also interesting.

Actually, the larger question is very interesting to me, and one I’ve spent my own share of time pursuing. But my days are currently taken up by long-put-off tasks. I will try to add some sketchy remarks.

Projects giving a central place to computation in scientific inquiry go back to Hobbes and Leibniz, at least, and then came Babbage and Peirce. One of the first issues determining their subsequent development is the degree to which one identifies computation and deduction. The next question concerns how many types of reasoning one counts as contributing to the logic of empirical science:

(1) Is deduction alone sufficient?

(2) Are deduction and induction irreducible to each other and sufficient in tandem?

(3) Are there three irreducible types of inference: abduction, deduction, induction?

Pingback: Abduction, Deduction, Induction, Analogy, Inquiry : 26 | Inquiry Into Inquiry

Nice links, but how should one have a discussion if already any single of those links would take hours to read (or even browse for something enabling an interesting discussion). So the idea is probably that everyone should try to discuss their favorite pet peeve…

Chazelle first talks about how incredible it is that Gordon Moore’s prediction of geometric growth has hold up for decades, but will soon be over, and therefore algorithms will move to center stage. But then he fails to even mention the most critical part where algorithms have to take over from Moore’s law in its old form: the sequential speed of computers is no longer increasing, instead the number of processing units goes up and the surrounding architecture to enable scalable parallel speedup improves.

So if algorithms want to take over where Moore’s law left us today, at least they should not completely ignore parallelism. Avi Wigderson at least mentions parallelism a couple of times, but it is certainly not one of the main topics.

And here is one of my pet peeves:

uniform-NC1 = ALogTime ?=? DLogSpace = L

OK, I admit that this won’t help to take over from Moore’s law either. But it could help to get into the mindset of parallism and its open theoretical questions.

Dear gentzen,

Good point. Anyway, my proposed specific discussion was about Avi’s statement that integrating insights from the theory of computation into the other sciences is very important (and even marks a scientific revolution). Reading Avi’s paper http://www.math.ias.edu/~avi/PUBLICATIONS/Wigderson2018.pdf can be useful but discussing the matter from scratch without reading anything may also work.

Parallelism is a great topic, how it should be studied in theory, what is the connection to practice (computers and computation in practice) and how parallelism is related to applications of ToC in theories of nature.

I’ve only had a chance to scan the “On the Nature of the Theory of Computation” (OtNotToC) chapter so far. There is of course a good dose of TOC but very little on the brand of World-Objective Contact (WOC) we’d need to connect with empirical science. Just on that sample it reminds me of projects like Wolfram’s “New Kind Of Science”. They do a good job of convincing us to use computational media as virtual laboratories for conducting experimental mathematics, but they leave us hanging when it comes to analyzing the relationship between what goes on inside the box of computation and the natural world outside the box.

Pingback: Abduction, Deduction, Induction, Analogy, Inquiry : 27 | Inquiry Into Inquiry

Pingback: Computer Science and its Impact on our Future | Combinatorics and more

Pingback: Must-read book by Avi Wigderson | Combinatorics and more