6 ms·

I'd say that all foundations are mathematical (at least for 'concrete' stuff, and more besides). If lisp was foundationaly interesting presumably mathematicians

I'd say that all foundations are mathematical (at least for 'concrete' stuff, and more besides). If lisp was foundationaly interesting presumably mathematicians would have given it more study? (perhaps they did?) I would disagree that computation is process for doing math - it is math in its own right, specifically that for operating over a discrete state space (urgh help needed to tighten this statement up) LC is basically a rewrite engine, so I'm not sure it would be so hard to implement? Probably some plastic bags, in two colours, paper scraps, and a marker pen would do it? (Edit - one colour bag would need 2 ordered compartments - or if you really have lots of spare time you could build it all with just plain bags and some set theory) However as you say perhaps Lisp is a better abstraction over the Turing tape (yuck).

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.
openfuture 4y ago
Lisp is called the dyck language or the catalan numbers depending on what kind of mathematician you are talking to.

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.

openfuture 4y ago

Lisp is called the dyck language or the catalan numbers depending on what kind of mathematician you are talking to.