4 ms·

The point that what gets published adapts to the state of the art is fair. Personally I think its adaptations for ANNs and interaction nets are more interesting

The point that what gets published adapts to the state of the art is fair. Personally I think its adaptations for ANNs and interaction nets are more interesting than the quantum ones. Once it has to account for the topology of the computer, or deal with non-atomic and continuous substrates, it changes a little bit. But this is orthogonal. The point wasn't that you can't make it adapt, I hope it doesn't come across like I'm dismissing the field and its importance. What I'm trying to say rather specifically is that it's not it's not about studying the nature of computation. It lives at a different level of theory than that. It might just be a disagreement on the article being used. I think it would be fair to say it studies a nature, just not the nature, but that would be true of all fields of CS.

pron 2mo ago
I would say that it very much is about the nature of computation, but computation itself has always been tied to the physical. The physicality (even hypothetical physicality) is exactly what separates theoretical computer science from pure mathematics. Even the two primary resources that complexity measures - time and space - are tied to physical quantities.
- ux266478 2mo ago
  The distinction is certainly a fair one to make. The etymological root of computation is "done with mental labor", by way of "to clean a financial ledger" (although weirdly, this isn't the real root. Putare is botancial pruning. Computare is a metaphor created after it spent some time on the semantic treadmill.) Grounding it to the physical is perfectly sane, because that's historically how it's been used. That being said, a counterargument to press against this is that complexity theory doesn't restrict itself to physical or hypothetical physicality in its totality. As I mentioned, there are swaths of complexity theory work which bound quite far afield. The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation). Of course even beyond this, we're still not studying the nature of computation, we're studying the cost. While you might say that of course these things are tied thanks to physicality (I wouldn't agree that they're equivalent on this basis, but I don't think that's an interesting semantic argument), I did also mention Landauer's principle being plausibly challenged, which is further problematic for conflating the two. Computation being reversible where entropy isn't doesn't explode complexity theory, but it does drive a wedge between information in a computer-sense and information in a thermodynamics sense. At that point, we don't have the claim in the first place, it's just a false friend. Something to consider.
  - pron 2mo ago
    I'm not saying computational complexity restricts itself to the physically realisable, I said it's tied to it and so there will be more papers on models that have some correspondence with physical reality. > we're still not studying the nature of computation, we're studying the cost That is one way of studying the nature of things, sort of like the use of the Hamiltonian in physics, especially if you're interested in problems and classes of problems, and their broad similarities and differences via reductions, rather than in specific computations. > The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation). Hypercomputation isn't really a big part of the main thrust of complexity theory, but (computable) oracles do very much play an important role in complexity theory, even in its lowest complexity classes, such as in the relativisation barrier, which shows that some proof techniques cannot separate P from NP. > I did also mention Landauer's principle being plausibly challenged, That's not complexity theory, at least not the standard theory, which treats time and space (or circuit size) more abstractly than concrete physics. There are, however, theoretical reversible models, just note that they don't yield different "classic" deterministic complexity classes (i.e. they do not yield exponential differences).
    - ux266478 2mo ago
      Again, all fair. To simplify, my points are to demonstrate a confounding nuance, simple counterexamples where the arguments don't hold. > Hypercomputation isn't really a big part of the main thrust of complexity theory I don't mean to imply that it was, though the results are actually relatively important elsewhere. > That's not complexity theory, at least not the standard theory, which treats time and space (or circuit size) more abstractly than concrete physics. More, but not totally abstractly. Steps and cells being vacuous primitives, they're not literally space-time, but within orthodoxy there's absolutely a partial morphism that's implied. That's why they're named like that. You are supposed to have them live close together in your head. >There are, however, theoretical reversible models, just note that they don't yield different "classic" complexity classes I know that some don't, but for example quantum models to use your own example, while not technically reversible in the absolute sense, do possess some reversibility capability and do derive different complexity classes. I think it's very obvious that there should be reversible computational models which yield different complexity classes from the typical ones. To me for a field to qualify as a study on the nature of computation, it should probably be able to design one totally a posteriori, if in a higher order language. Complexity theory might be invoked in such a construction, but it's not the one doing the building. It's one of many in an orchestra. Here's a question I have, since you do seem pretty well versed on CT. Universal quantification over complexity classes of first-order systems, used anywhere in the abstract?

pron 2mo ago

I would say that it very much is about the nature of computation, but computation itself has always been tied to the physical. The physicality (even hypothetical physicality) is exactly what separates theoretical computer science from pure mathematics. Even the two primary resources that complexity measures - time and space - are tied to physical quantities.

ux266478 2mo ago
The distinction is certainly a fair one to make. The etymological root of computation is "done with mental labor", by way of "to clean a financial ledger" (although weirdly, this isn't the real root. Putare is botancial pruning. Computare is a metaphor created after it spent some time on the semantic treadmill.) Grounding it to the physical is perfectly sane, because that's historically how it's been used. That being said, a counterargument to press against this is that complexity theory doesn't restrict itself to physical or hypothetical physicality in its totality. As I mentioned, there are swaths of complexity theory work which bound quite far afield. The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation). Of course even beyond this, we're still not studying the nature of computation, we're studying the cost. While you might say that of course these things are tied thanks to physicality (I wouldn't agree that they're equivalent on this basis, but I don't think that's an interesting semantic argument), I did also mention Landauer's principle being plausibly challenged, which is further problematic for conflating the two. Computation being reversible where entropy isn't doesn't explode complexity theory, but it does drive a wedge between information in a computer-sense and information in a thermodynamics sense. At that point, we don't have the claim in the first place, it's just a false friend. Something to consider.
- pron 2mo ago
  I'm not saying computational complexity restricts itself to the physically realisable, I said it's tied to it and so there will be more papers on models that have some correspondence with physical reality. > we're still not studying the nature of computation, we're studying the cost That is one way of studying the nature of things, sort of like the use of the Hamiltonian in physics, especially if you're interested in problems and classes of problems, and their broad similarities and differences via reductions, rather than in specific computations. > The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation). Hypercomputation isn't really a big part of the main thrust of complexity theory, but (computable) oracles do very much play an important role in complexity theory, even in its lowest complexity classes, such as in the relativisation barrier, which shows that some proof techniques cannot separate P from NP. > I did also mention Landauer's principle being plausibly challenged, That's not complexity theory, at least not the standard theory, which treats time and space (or circuit size) more abstractly than concrete physics. There are, however, theoretical reversible models, just note that they don't yield different "classic" deterministic complexity classes (i.e. they do not yield exponential differences).
  - ux266478 2mo ago
    Again, all fair. To simplify, my points are to demonstrate a confounding nuance, simple counterexamples where the arguments don't hold. > Hypercomputation isn't really a big part of the main thrust of complexity theory I don't mean to imply that it was, though the results are actually relatively important elsewhere. > That's not complexity theory, at least not the standard theory, which treats time and space (or circuit size) more abstractly than concrete physics. More, but not totally abstractly. Steps and cells being vacuous primitives, they're not literally space-time, but within orthodoxy there's absolutely a partial morphism that's implied. That's why they're named like that. You are supposed to have them live close together in your head. >There are, however, theoretical reversible models, just note that they don't yield different "classic" complexity classes I know that some don't, but for example quantum models to use your own example, while not technically reversible in the absolute sense, do possess some reversibility capability and do derive different complexity classes. I think it's very obvious that there should be reversible computational models which yield different complexity classes from the typical ones. To me for a field to qualify as a study on the nature of computation, it should probably be able to design one totally a posteriori, if in a higher order language. Complexity theory might be invoked in such a construction, but it's not the one doing the building. It's one of many in an orchestra. Here's a question I have, since you do seem pretty well versed on CT. Universal quantification over complexity classes of first-order systems, used anywhere in the abstract?