Timeline for Why are computable functions also called recursive functions?
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 23, 2017 at 11:25 | comment | added | Alexey | IMO this question is answered, for example, in The theory of recursive functions, approaching its centennial by Kleene. | |
| Jan 14, 2016 at 17:45 | comment | added | Golo Roden | Oh, I think that there's a hidden meaning in way more terms than one might think… otherwise there would be no need to think of a name, we could just assign numbers to the things ;-) | |
| Jan 14, 2016 at 8:02 | comment | added | Raphael | @GoloRoden It's also important not to get frustrated looking for meaning where there is none, e.g. "dynamic programming" and others. | |
| Jan 14, 2016 at 7:12 | comment | added | Golo Roden | @Raphael Sorry for not being able to come up with a better formulation if you don't have a CS degree… and no, for me that's just saying "it is like it is because it is like it is". That's no explanation, that's just a definition (and I know that a definition per se is like it is, but there will probably be a reason why it is like it is, and I wanted to know that reason, not somebody who points me to the definition which I already mentioned.) | |
| Jan 13, 2016 at 23:28 | answer | added | Nikos M. | timeline score: 0 | |
| Jan 13, 2016 at 23:23 | comment | added | Nikos M. | because theyr are defined recursively, i.e "more complex functions are defined in terms of previously defined, simpler functions" | |
| Jan 13, 2016 at 7:05 | comment | added | Raphael | "computable functions are also called recursive functions [...] What is the actual meaning of recursive in the context of computability?" -- the inaccuracy in the first part aside, have you not just answered your own question? Anyway, our reference question has fitting answers. | |
| Jan 13, 2016 at 7:05 | history | edited | Raphael |
edited tags; edited tags
|
|
| Jan 13, 2016 at 5:04 | vote | accept | Golo Roden | ||
| Jan 13, 2016 at 4:56 | comment | added | Golo Roden | @Auberon Thanks, IMHO this comment explains it the best so far :-) | |
| Jan 13, 2016 at 1:38 | comment | added | Auberon | @GoloRoden Note that the tag-description of 'computability' (you used it for this question) says: "computability theory a.k.a. recursion theory". Gödel termed functions recursive, but the term evolved to computable. Probably to avoid confusions like yours. People who study computability theory (intensively) tend to use the term recursion theory more as to 'respect' its roots. | |
| Jan 13, 2016 at 1:28 | answer | added | Auberon | timeline score: 17 | |
| Jan 13, 2016 at 1:06 | answer | added | Kaveh | timeline score: 21 | |
| Jan 13, 2016 at 0:16 | history | tweeted | twitter.com/StackCompSci/status/687065619397783552 | ||
| Jan 12, 2016 at 23:42 | answer | added | Yuval Filmus | timeline score: 9 | |
| Jan 12, 2016 at 22:53 | comment | added | Hendrik Jan | Waht about primitive recursive functions? Copied from wikipedia they are defined as $h(0,x_{1},\ldots ,x_{k})=f(x_{1},\ldots ,x_{k})$ and $h(S(y),x_{1},\ldots ,x_{k})=g(y,h(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$. That is a function that calls itself. | |
| Jan 12, 2016 at 21:50 | comment | added | Thomas Klimpel | They cheat, because they include the μ operator. This is a minimization operator, but of course minimization has very little to do with recursion. So it seem like somebody (Kleene) thought that "recursive" would sound nice, so he invented an excuse for using that name. Much later, Robert Soare explained that "computable" would sound much better, and that "recursive" had just been a marketing trick of the early days, and everybody agreed. | |
| Jan 12, 2016 at 21:33 | comment | added | Golo Roden | Sorry, but that doesn't help or explain anything, if you do not know yet what "recursive" in the context of computation means. | |
| Jan 12, 2016 at 21:02 | comment | added | Thomas Klimpel | μ-recursive function | |
| Jan 12, 2016 at 20:14 | review | First posts | |||
| Jan 12, 2016 at 23:28 | |||||
| Jan 12, 2016 at 20:12 | history | asked | Golo Roden | CC BY-SA 3.0 |