4 ms·

> I would disagree that computation is process for doing math Sorry, but you are mistaken. This is not a matter of opinion, it is a matter of historical fact.

by lisper 4y ago

> I would disagree that computation is process for doing math Sorry, but you are mistaken. This is not a matter of opinion, it is a matter of historical fact. There is a reason that the title of McCarthy's original Lisp paper ends with "and Their Computation by Machine." The opening paragraph of Turing's 1936 paper ends with the sentence, "According to my definition, a number is computable if its decimal can be written down by a machine." > specifically that for operating over a discrete state space. Sorry, but you are mistaken about that too. Analog computers and quantum computers are computers but they do not operate over discrete state spaces. They are, however, machines.

somewhereoutth 4y ago
I think I meant computation in the mathematical sense. In other words that 'computation' is a mathematical object worthy of study in its own right. Per analog and quantum, indeed, and they are also mathematics. I think that is my point - (very nearly) everything proceeds from mathematics, there is no other foundation.
- lisper 4y ago
  What can I say? You are mistaken. Computation is as much about physics as it is about math. It is the study of what can actually be done in this universe with real hardware (including human brains). If you doubt this, read the opening paragraph of this paper: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf The only reason that P=NP? matters at all (let alone why it is a foundational question) is because the theory of computation concerns itself with what can be done with actual physical hardware in actual physical time. > Per analog and quantum, indeed, and they are also mathematics. No, they aren't. Analog computers are machines. Quantum computers are machines (or at least they will be if we ever actually manage to build one). We can describe the behavior of these machines mathematically, but that is not why they matter. They matter because we can actually build them.
  - somewhereoutth 4y ago
    I agree that much of the motivation comes from real world imperatives, but, for example, P=NP is of deep mathematical interest in its own right, and if/when mathematicians solve it, they will move on and let us sort out the details. We can actually build stuff (beyond some somewhat blessed prototypes) often only when we've understood the mathematics behind it - edit: or is that the other way around?? I'm not sure that any rigorous discipline can consider itself outside or unbound by mathematics.
    - lisper 4y ago
      > P=NP is of deep mathematical interest in its own right Sure. Computation and math are closely related, but they are not identical. Physics is described almost exclusively by differential equations, but differential equations and physics are nonetheless two distinct fields of study.
  - kazinator 4y ago
    The complexity topic from which we have P = NP is not actually about time, but number of steps. Of course that matters physically because if you only have a machine that performs one step at a time (or a somewhat better one that performs N steps at a time, for some fixed N), then the number of steps does translate to amount of time. If you have access to unlimited parallelism, then, for instance, some recursive algorithms that completely process a tree structure can drop from linear time to logarithmic.
    - lisper 4y ago
      > Of course that matters physically because if you only have a machine that performs one step at a time (or a somewhat better one that performs N steps at a time, for some fixed N), then the number of steps does translate to amount of time. It's much more fundamental than that. If you have any finite machine then the amount of time it takes to perform N steps will be proportional to N for sufficiently large N. > If you have access to unlimited parallelism... And if you had some magic pixie dust... Sorry to be the one to break this to you but you live in a finite universe.

by lisper 4y ago

somewhereoutth 4y ago

I think I meant computation in the mathematical sense. In other words that 'computation' is a mathematical object worthy of study in its own right. Per analog and quantum, indeed, and they are also mathematics. I think that is my point - (very nearly) everything proceeds from mathematics, there is no other foundation.

lisper 4y ago
What can I say? You are mistaken. Computation is as much about physics as it is about math. It is the study of what can actually be done in this universe with real hardware (including human brains). If you doubt this, read the opening paragraph of this paper: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf The only reason that P=NP? matters at all (let alone why it is a foundational question) is because the theory of computation concerns itself with what can be done with actual physical hardware in actual physical time. > Per analog and quantum, indeed, and they are also mathematics. No, they aren't. Analog computers are machines. Quantum computers are machines (or at least they will be if we ever actually manage to build one). We can describe the behavior of these machines mathematically, but that is not why they matter. They matter because we can actually build them.
- somewhereoutth 4y ago
  I agree that much of the motivation comes from real world imperatives, but, for example, P=NP is of deep mathematical interest in its own right, and if/when mathematicians solve it, they will move on and let us sort out the details. We can actually build stuff (beyond some somewhat blessed prototypes) often only when we've understood the mathematics behind it - edit: or is that the other way around?? I'm not sure that any rigorous discipline can consider itself outside or unbound by mathematics.
  - lisper 4y ago
    > P=NP is of deep mathematical interest in its own right Sure. Computation and math are closely related, but they are not identical. Physics is described almost exclusively by differential equations, but differential equations and physics are nonetheless two distinct fields of study.
- kazinator 4y ago
  The complexity topic from which we have P = NP is not actually about time, but number of steps. Of course that matters physically because if you only have a machine that performs one step at a time (or a somewhat better one that performs N steps at a time, for some fixed N), then the number of steps does translate to amount of time. If you have access to unlimited parallelism, then, for instance, some recursive algorithms that completely process a tree structure can drop from linear time to logarithmic.
  - lisper 4y ago
    > Of course that matters physically because if you only have a machine that performs one step at a time (or a somewhat better one that performs N steps at a time, for some fixed N), then the number of steps does translate to amount of time. It's much more fundamental than that. If you have any finite machine then the amount of time it takes to perform N steps will be proportional to N for sufficiently large N. > If you have access to unlimited parallelism... And if you had some magic pixie dust... Sorry to be the one to break this to you but you live in a finite universe.