undefined | Better HN

0 pointssomewhereoutth3y ago0 comments

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).

0 comments

4 comments · 2 top-level

lisper3y ago· 2 in thread

> 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.

somewhereoutthOP3y 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.

lisper3y 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

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.

3 more replies

openfuture3y ago

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

j / k navigate · click thread line to collapse