Talk:Double recursion

Comments

Oooh, this is a badly written article. It's simple, there are two iterators, but not yet an Ackermann function. I mean this double recursion still defines a primitive recursive function! Only as soon as the two iterator parameters are defined with the same variable is it an Ackermann function. I mean if you'd define an Ackermann function like is done here (a function index is a function variable) then in a sense Hilbert already defined such a function in his "On the Infinite" article that was the inspiration for Ackermann. I suppose we just have to follow the definition of Rozsa Peter and not much additional speculative talk. But it takes an overhaul of the page and for me if I'd do it the moderators would undo this again so I won't. Credentials eh? --Gerard van Novaloka (talk) 21:19, 12 February 2011 (UTC)[reply]

No, please feel free to edit the article. On remote articles like this, few people watch them and so you actually have some freedom to rework them if you want. I work in computability but I view this sort of topic as mostly historical, and I have no idea what Robinson might have called "double recursion" so I have no way to updating the article without looking it up. But the final function does seem to be Ackermann's function, unless I am missing something. — Carl (CBM · talk) 22:52, 12 February 2011 (UTC)[reply]

Yes please feel free to contribute, I originally wrote this article because I had run into the term doubly-recursive functions without explanation many times in historical literature and had no idea what it was. I traced a definition back to Robinson, but I'd love to hear more about the topic. Cheers, — sligocki (talk) 02:21, 14 February 2011 (UTC)[reply]

Yes, it is historical and I have Péter's book "Recursive Functions" here, so I will look it up and can make a nice contribution. But I still have to come to grips with the term Ackermann function. What exactly is it? Ackermann defined the two iterators of the double recursion both by a single variable, so the original Ackermann function is different from what we've come to understand it is (as in the article which is not so badly written as I first thought). Of course the initial value of the first (primitive recursive) iterator doesn't actually contribute much to the speed of the function. I'll see what Rózsa Péter has to say as she introduced the term "double recursion". --Gerard van Novaloka (talk) 21:19, 17 February 2011 (UTC)[reply]

You have quite a discussion at the Ackermann function but it misses the actual new function Ackermann made. "From Frege to Gödel" has all the original articles. Hilbert in "On the Infinite" defined a recursive scheme that is essentially the same as Knuth's arrows a^^...b [^#c] (only difference is that it starts with addition instead of multiplication at c=0), which we now call an Ackermann function. What Ackermann in "On Hilbert's construction of the real numbers" did was change the scheme, add in an extra initial condition of his own, and form a 3-valued function called φ(a,b,c). But the proof that there was a function which grows faster than any primitive recursive function was only acceptable for functions of 1 variable, so Ackermann created just that by having ψ(a) = φ(a,a,a) and that is strictly the only novel function of Ackermann at this level. Same is the case with the term "up-arrows" or Knuth's up-arrows or even worse "Knuth's up-arrow notation" while Donald Knuth called them (once) "arrow functions" in his original 1976 popular article and Conway adopts the term "arrows" in his 1996 Book of Numbers, explaining that nowadays only the arrowhead ^ remains. It's hard to be precise, but as the Wikipedia sets the norm it shouldn't think that by adding more words a concept is better explained. --Gerard van Novaloka (talk) 21:49, 17 February 2011 (UTC)[reply]

I must add that I wish I'd knew what Ackermann is doing in the latter part of his 1928 article! We meet ψ(a_i,...) [a_i#k] functions there, but his exposition is so obscure. Perhaps only very few people have ever read and understood this article in full, all the nitty-gritty details. They just take the conclusion for granted, which was obvious from the start... (that there are functions which grow faster than any primitive recursive function)... --Gerard van Novaloka (talk) 22:16, 17 February 2011 (UTC)[reply]

I did check the paper given in this article, which did give the example function that is stated here. I have been told that the function people usually call the Ackermann function is not the same as what Ackermann actually defined. If you can make sense of it, by all means please try to clarify the articles. — Carl (CBM · talk) 00:06, 18 February 2011 (UTC)[reply]

Hi, I've decided not to write for the Wikipedia any more, because my stuff gets removed too often. I hate being just a lurker of information, but sometimes it's a waste of effort trying to contribute. Especially in Holland moderators seem to think their pages are pure gold, while in the beginning of the Wiki people just wrote what they liked. What I've noticed is also that true knowledge is a volatile thing, I mean, things aren't what they seem to be when you study the matter. Take the supposed sign of a million on pharaoh Narmer's macehead, look closely, what do you see? Just an example. --Gerard van Novaloka (talk) 17:48, 25 February 2011 (UTC)[reply]