Talk:Double recursion

Mathematics Stub‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

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 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" I guess.