Hacker News new | ask | show | jobs
by ASipos 2801 days ago
> a field as esoteric as “recursive function theory”

How can this kind of descriptions persist when recursive functions are the very thing that a computer computes.

2 comments

Are they? They are the very thing that lambda calculus models computation on. They are not the very thing that Turing Machines model computation on. They also are not the very thing that CPUs use, or that assembly uses, or even that most high-level languages use. (Unless you're going to say that most high-level languages use a recursive descent parser to generate the binaries that the CPUs run, and that's the basis for your statement...)
Neither lambda calculus, nor Turing machines "model computation on" recursive functions. Rather, these two, and all the other models of computation are equivalent as they compute the same class of functions from the naturals to the naturals. And we call that class the class of recursive functions.

That being said, a computer is a physical device that is able to compute this entire class of recursive functions. It is what makes it a computer and not a pen or a chair. It's not some esoteric notion. It's the whole thing about it.

That's like saying that the basis of computation is the standard model, since all actual physical computers are made out of particles that are in the standard model. It may be true, but it's so far abstracted from what's actually going on that it's not useful at all.
Because rft is esoteric.

A lot of more applied CS departments don't require a CS theory course, and many programmers didn't major in CS or never attended university.

So there are far more computer programmers than there are people who know what recursive function theory is or how it relates to modern computers.