I am trying to sharpen the convex hull of what seems like a (surprisingly) stubborn concept to enclose based on answers here, as well as conversations with others, around the nature of what actually constitutes a computation.

As a motivating scenario for the question, consider the following:

Around some distant star in a some faraway godforsaken galaxy, exists a boring gas cloud. Here, two protons careen towards each other on an inevitable collision course. The protons' repel each other, and their trajectories inevitably change and off they go.

Has a computation taken place?

  • 3
    $\begingroup$ Luckily for us, in TCS "computation" is just a word for the process that a computer does when it executes, and a "computer" is a well-defined mathematical abstraction (e.g. a Turing Machine). Not a physical device, so from this perspective, physical processes do not do computation, and the answer to your question would be no, and furthermore, what normal people call computers (actual computers) don't do computation either. If you want to reason about the real world or physics as it models the real world, maybe you should ask a philosopher or a physicist how they define "computation"? $\endgroup$
    – Neal Young
    Oct 12, 2021 at 2:53
  • $\begingroup$ @NealYoung To make sure I understand you: Are you claiming that there exist a multitude of (possibly contradictory) formal definitions of computation? $\endgroup$
    – dnnct
    Oct 12, 2021 at 14:46
  • $\begingroup$ No, just that TCS has one. I can't speak for other fields. And implicitly I am suggesting that there are philosophical (and somewhat gray) issues when applying any formal concept and asking whether a given real-world situation actually realizes it. Or for that matter, any concept, formal or otherwise. Our conceptual world only provides models. Models are never the same as the underlying reality. And probably "underlying reality" is itself never precisely knowable. $\endgroup$
    – Neal Young
    Oct 12, 2021 at 19:37
  • $\begingroup$ @NealYoung Ok - if we focus on the definition you provided for TCS, then it seems like you're saying that it does not make sense to even talk about computation, without talking about mathematical abstractions. However mathematical abstractions are mental models, hence, it does not make sense to talk about computation, without invoking a being that possesses mental models and the capacity to create mathematical abstractions to begin with. $\endgroup$
    – dnnct
    Oct 13, 2021 at 1:34
  • $\begingroup$ Strange, I do it all the time with other people, and we don't seem to have trouble making sense of it. On the other hand, I don't know how to talk about, say beings, and feel like I'm making sense quite so precisely. Perhaps mathematics is the only domain where the kind of precision your question seems to be asking for seems possible, and maybe that's because mathematicians are seeking exactly that kind of thinking. :-) $\endgroup$
    – Neal Young
    Oct 13, 2021 at 1:43