Comment by pron | Hacker News Reader

Comment by pron | Hacker News Reader

Parent Full thread

> You can't have a theory of computation without mathematics.

You're right that you can't have a theory without some language to talk about it (and it also requires people to come up with it, so is psychology more fundamental than physics?), but the theory of computation is about the laws that govern the power of mathematics. I.e. mathematics (and the universe) was constrained by computation long before anyone knew that. On the other hand, Turing was very careful not to rely on any mathematical and even logical results in his 1936 paper, not even on the principle of explosion (which is used in modern formulations of the halting theorem), precisely because he knew he wanted to get at the fundamental limitations of the very process of deduction itself (he does say that the theorem can be proven using the principle of explosion, but that would be "unsatisfying"). Turing showed that if a premise can be written as some string of symbols and so can the conclusion, then, due to constraints on the mind and body of the mathematician writing them, the process of deduction is subject to the laws of computation. This applies without any need to describe what the symbols represent, if they represent anything at all.

While the theory of computation does use concepts such as functions or sets, it knowingly treats them as higher level ideas than computation. I.e. a number or a set or a function is a name given by humans to something that can be computed or an abstraction of such a thing (so we can talk of non-computable things).

And if you want to include TOC as part of mathematics (some do, some don't), then it is its most fundamental part, more fundamental than formal logic (some people include that in mathematics, but most don't), which is subject to the laws of computation but not vice-versa.

Psychology and physics are two independent and different fields. Physics wasn't built on top of psychology and vice versa. What language of psychology do you need to talk about physics and vice versa? Newtonian physics and einstein physics or quantum physics may be better examples? Or psychology with developmental psychology, behavioral psychology, etc.

Are you saying Turing, the world famous mathematician, didn't use any mathematical ideas? Are you talking about "On Computable Numbers, with an Application to the Entscheidungsproblem" where he laid out the algorithm to the Turing machine? Are you saying there was no logic behind the Halting Problem? You do realize that his 1936 was filled with mathematical proofs? The paper you referenced is one of the world's most famous mathematical papers. Just because it isn't full of numbers doesn't mean it's not mathematics. Do you think Euclid's elements is part of mathematics?

> Are you saying Turing, the world famous mathematician, didn't use any mathematical ideas?

Of course he did, but his ideas also came to him through psychology and he expressed them in English. That doesn't make psychology or English more fundamental than computation. Because humans create theories and humans are very complex, almost everything human is involved in the construction of theories, but when we talk about something being more fundamental than another we're not talking about the human process of the theory's construction but about the subject matter of the theory. The theory of computation is not only concerned with matters at a "lower-level" than mathematics, but also lower than logic.

In fact, that computation can be described using mathematics (or English) is precisely because of Turing's discovery of universal computation, which means that any system of symbols that's "rich enough" can describe any other.

> You do realize that his 1936 was filled with mathematical proofs?

Ah, but you should take a closer look at them. His proof of what we today know as the halting theorem goes to great lengths to avoid using any logical axioms. There's a great paper about that by the Turing scholar, Juliet Floyd (https://mdetlefsen.nd.edu/assets/201037/jf.turing.pdf esp. §4.5). He did that because he was trying to get to an idea that's even more fundamental than logic.

> Just because it isn't full of numbers doesn't mean it's not mathematics.

As I said, some people do consider formal logic, and even computation as branches of mathematics (though others don't), but if so you can think of computation as more fundamental than any other branch. Let me put this more precisely instead of speaking in the abstract: computation is more fundamental than the natural numbers (the axiom of infinity, often considered the most basic mathematical axiom) and even the most basic axioms of logic, such as the principle of explosion, in the sense that neither can be given a precise sense without computation, but computation is described without them.

Reply on news.ycombinator.com