Computation as a universal and fundamental concept

sgt101

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.

summarybot

What even is computation? State-based inference. But intelligence itself does not rely on computation, only its biological counterweight seems to and only in certain situations. If Computation is a "Universal Concept" then there are at least 4 or 5 more "Universal Concepts" analogous to intuition and spontaneity.

jojogeo

Something has always nagged me about the halting problem, might be my mis-understanding of the problem space but; - You have a piece of software - That software does in memory compute only - The software does not touch any peripherals, networking, or any other external source which introduce unpredictability (x) I'm convinced that somehow this can be solved/proven whether the execution will halt or not. (x) The second you touch any external peripherals or networking, you're effectively asking the question of "If I phone my friend, will they pick up the phone?" -> to which the only answer is, "They'll pick it up, only if they pick it up/are there". You can't answer that question without trying it. Am I missing the point? I'm sure you can introduce other edges even in the limited model above, e.g. where a memory stick stops responding or something; but all in if you have reliable kit and don't touch anything external, why can't this be solved?

quux0r

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.

ChrisArchitect

Related: Ergo: Long Form Philosophy Lectures https://news.ycombinator.com/item?id=48840497

sim04ful

I really do think matter wants to be sentient, being sentient is natural. Why i think that exactly, i'm not sure why, it just seems intuitive.

jdw64

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 things, they're subject to physical laws. Still, whether that makes them fundamental is a difficult question. I think these are just results of the process where humans name phenomena and constrain them. I don't think they're the cause. You can define computation broadly enough, as 'a process where a state changes to another state according to rules,' to make almost everything look like computation. But being able to explain something with computation and claiming that computation is fundamental are different things, aren't they? Meaning exists within the structures and constraints of human-made formalisms. We artificially lower cognitive complexity and translate things into human language. Whether that's fundamental, I'm not sure. Maybe I'm a reductionist. Plenty of intellectually brilliant scholars make those claims, but people like me, with slower minds, end up thinking these kinds of stupid thoughts. I wish I could organize my own thoughts bette

jeffrallen

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.

__rito__

From the site's "About" section: > "Ergo is a nonprofit that publishes long-form philosophical lecture courses with leading scholars. Everything we publish is freely available, without ads or paywalls." I know what to do this weekend if it rains!

sdevonoes

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”?)

Diogenesian

There are a lot of long comments basically saying what I am about to say so I will try to keep this brief: Computation is a metaphysically universal and fundamental concept, since metaphysics is (tautologically) the domain of humans and we use symbolic communication. So of course very general theories of symbolic processes (e.g. Turing machines) are pertinent to the symbolic methodology we use to understand scientific processes. But it is a fundamental mistake to jump from that to saying computation extends to a law of the universe. Computation reflects laws of the universe, but only in the exact same way that scientific and mathematical human speech do. The mystery (still totally unsolved) is how humans are able to intuitively understand space / time / causality / etc in order to define coherent symbolic rules that reflect real processes. That computers can seemingly always implement these rules having been given the symbols is of philosophical/scientific interest, but it's solipsistic to say it's a fundamental concept of the universe.

vatsachak

Computation is in the eye of the beholder

lo_zamoyski

I'd have to look deeper into his views, but I've already come across what seem like similar claims that try to attribute computation to the laws of physics or to matter in general or whatever. However, these rest on category errors. Consider two characterizations of computation: 1. A mental process constituted by logical and intentional acts. 2. A mathematical model or formalism (or a set of formally equivalent formalisms). In the case of (1), intentionality rules out computation as an extra-mental phenomenon. Things in the world aren't about something else; they just are what they are. But computation as a mental act is about something else. To claim otherwise would be like claiming deduction is a broad feature of reality, which is effectively some kind of panpsychism. In the case of (2), if it's a mathematical model, then either by definition it doesn't exist outside the mind as such, or it must be instantiated in some objective manner. The trouble with finding instantiations is that it's not clear what constitutes an instantiation. Can you find correspondences? Sure. In fact, our physical computing machines correspond to these models in some way. But instantiation is more than mere correspondence, and this becomes even more the case when you consider that the lambda calculus corresponds to the Turing machine. Another problem is that even mathematical models of computation cannot be said to encode mathematical operations as such. Is a Turing machine moving symbols around on an abstract tape actually adding two numbers? I would say that it is merely simulating the addition by producing results that afford that kind of interpretation.

kaashif

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.

quantum_state

Would like to think we human are better than what is implied by the course in that we would not mistaken our model of reality as reality itself.

dboreham

I saw the title and assumed an article by Wolfram. But it's by Tim Roughgarden who I know from algorithmic game theory. Anyway, I'll register my membership in the "it's more fundamental than that" camp.