Tim Roughgarden Explores the Limits of Computation and the P vs NP Mystery

For those that are unfamiliar, Tim Roughgarden is a phenomenal instructor, and has made significant contributions to the field of algorithmic game theory, which has strong connections to a lot of the work he appears to be doing here. I highly recommend his excellent introductory lectures on the subject, especially if you're interested in pursuing his ideas here more rigorously: https://www.youtube.com/watch?v=TM_QFmQU_VA&list=PLEGCF-WLh2...

His website also hosts a bunch more work as well as various lecture notes and exercises: https://timroughgarden.org/

Tim's lectures helped me a lot during my PhD when I was getting up to speed on this subject, and some of the more nuanced ways that computer scientists have worked with these broad algorithmic problems.

Computation has turned out to be a far more general concept than I think was imagined, up to the point that many computer scientists now seem to equate computation with the functioning of the universe. Recently it's been shown that there are real, physical processes which are undecidable (we cannot know if a latice of atoms has a spectral gap or not, we cannot determine if a specific particle in a fluid flow will reach a specific place or not, we cannot determine if a ray of light will reach a specific target in certain configurations of reflection).

Our world appeared computable, but it isn't, even if P=NP.

I like how every time a new technology is invented and becomes big, people start to think it explains everything. Like how in the 16th/17th centuries some people thought the universe was a big clock. Or how in the 19th centuries people thought the universe was like a big steam engine. Or now we think the universe is a big computer.

Not saying this is wrong or that I've watched all of the lectures above or anything, but it's just funny to imagine that aliens might look at us the same way we could look at a monkey society saying that the universe is like a big one of those rocks they use to smash nuts open.

Computation and information really does seem universal though, so this is just a funny thought and not serious commentary.

Discrete math and Algorithms were two of my favorite college classes. They were really the only part of computer science that was mind blowing. The rest was software engineering, which was transparently "possible". Like, yes, big programs and OSs and numerical models exist, and yes I will graduate and work with them and add to them, someday, yeah sure.

But decidabilty, Godel's theorm, busy beaver numbers, etc... those were unexpected and worth the price of admission.

Thanks Prof Hadas, you made it fun to have my mind blown.

Is 'computation' really universal and fundamental? Turing machines, lambda calculus, algorithmic notations, they're all human-made formalisms. Are the halting problem and the limits of computability actually constraints that exist only within these human-made formal systems?

When we constrain a formalism to reduce complexity, it feels like necessity emerges from within those constraints. For example, when we say 'CRUD app,' we immediately think of a specific pattern. In the same way, once you adopt a 'form,' the constraints that come with that form progressively expand the state space. In that sense, it feels like both discovery and invention.

Famous mathematicians and scientists often distinguish between model and reality, yet we tend to mistake the model's shape for reality itself. People like John Wheeler and Stephen Wolfram argue that computation is a fundamental property of the universe. But can we really say that when we downcast reality to fit human cognition, losing information in the process, and then upcast it back, the information is fully restored? I always find this point difficult.

Landauer's principle says that abstract logical operations, information erasure, necessarily increase physical entropy. That shows there's a thermodynamic cost to physically implemented information processing. But I don't think that proves computation is fundamental.

Whether it's computation or geometry, they're all abstract formalisms created by humans. But when we actually measure t […]

From my naive pov: Related to computation is the concept of state (I know, functional languages can get away without it, sort of). I always wondered how the universe “knows” the mass of the sun. If there are some underlying functions/computations “running” in the background to keep planets moving and so on, and if the mass of planets is a key element in such computations… then either: the mass is calculated “on the fly” every time (seems expensive) or it’s a variable (how is it updated? Where is it “stored”?)

Computation as realized by computers is a formalism invented by Turing, Church, Kleene and others to make precise the intuitive notion of "algorithm".

An algorithm, at its root, is a procedure rooted in human understanding that human beings can follow.

When Turing and others first introduced this formal notion, not all mathematicians were even fully convinced it was an adequate representation of the informal intuitive notion. For example, some argued it was too broad because traditionally knowing that an algorithm eventually terminates was one of the requirements (to some) for something to be a legitimate algorithm. Why? Because the idea is rooted in human practical concerns and human understanding. Depending on what one cares about, one could actually reject the Turing formalization of algorithm on grounds of the class containing non-convergent (partial) functions.

All this is to say that "computation" is very much a human invention and little more than a formal model of human behaviors (we want to manipulate things algebraically). Elevating it to some objective substance of the universe is just doing 17th/18th century philosophical Idealism wrapped in new clothes.