The following is a conversation between Clyde Kruskal and Bill Gasarch.
CLYDE: Bill, a student, Ian Roberts, asked me if there are any non-primitive recursive functions that people actually want to compute. (See here for a definition of Primitive Recursive. Also see here for Ackermann's function which is computable but not primitive recursive.)
BILL: Off hand I would say no, but non-prim rec functions DO come up in natural ways.
CLYDE: That's not what he asked.
BILL: Even so, that's what I will blog about. OH, one more thing, why does he want to know?
CLYDE: Ask him directly. (BILL then emailed Ian)
BILL: Good question about NATURAL problems that are not prim-rec, but why do you want to know?
IAN: Meyer and Richie proved (see here) that if you limit the control flow to IF statements, FOR loops with finite iterators then the class of functions you implement is exactly the primitive recursive functions. So I was wondering if I could avoid ever using WHILE loops since they are harder to reason about.
BILL: YES you COULD avoid ever using WHILE LOOPS; however, there are times when using them is the best way to go.
CLYDE: Bill, when is the last time you wrote a program? And LaTex does not count.
BILL: Good point. Rather than take my word for it, let's ASK my readers. I'll add that to my list of RANDOM THOUGHTS ABOUT non-prim rec functions.
SO, random thoughts on non-prim rec functions
0) Are there problems for which writing a WHILE loop is the way to go even though they are not needed?
1) HALT is not prim recursive and we want to compute it. Oh well. All future examples will be computable.
2) QUESTION: Are there simple programming languages so that HALT restricted to them is decidable but not primitive recursive? I suspect one could contrive such a language so I ask for both natural and contrived examples.
3) The Paris-Harrington Numbers from Ramsey Theory are computable and grow MUCH faster than prim rec. Indeed- they grow much faster than Ackermann's function. See Wikipedia Entry.
4) The Kanamori-McAloon Theorem from Ramsey theory is computable and grow MUCH faster than prim rec. Indeed- they grow much faster than Ackemann's function. See Wikipedia Entry. They are not as well known as the Paris-Harrington numbers. Hopefully this blog post will help that.
5) Goodstein's Theorem yields numbers that are computable and grow MUCH faster than prim rec. Indeed, they grow much faster than Ackermann's function. See Wikipedia Entry and/or my blog post on them.
6) QUESTION: Of PH, KM, GOOD, which grows fastest? Second fastest? Third fastest? Perhaps some are tied.
6) QUESTION: We know that GO and CHESS have very high complexity, but are still prim recursive. We know that there are some math games (e.g., the Hydra game) that are not prim recursive. Are there any FUN games whose complexity is NOT prim recursive?
7) Tarjan's UNION-FIND data structure has amortized complexity roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's function. This is also a lower bound. See Wikipedia entry on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data structure actually used? It can be used to speed up Kruskal's MST algorithm, but that just takes the question back one step: Is MST a problem people really want to solve? I asked Lance and he asked chatty. For the results of that see here . The answer seems to be YES, though I wonder if the speedup that UNION-FIND gives is important. Union-Find is also used in the Hoshen-Kopelman Algorithm for (to quote Wikipedia) labeling clusters on a grid, where the grid is a regular network of cells, with the cells being either occupied or unoccupied. Other issues: (a) is UNION-FIND hard to code up? Lance tells me that it is easy to code up. (b) Is the constant reasonable?
8) Is the Ackerman Security Company called that since they claim that breaking their security is as hard as computing Ackerman's function? Unlikely- they spell it with only one n at the end. Even so, my class believed me when I told them that.
9) The finite version of Kruskal's Tree Theorem YADA YADA YADA not prim rec. Wikipedia Entry
CLYDE: You can't YADA YADA YADA my Uncle Joe!
BILL: It's my party and you'll cry if you want to, cry if you want to, cry if you want to. (See here for Leslie Gore's song Its my party and I'll cry if I want to which is not about non primitive recursive functions. Also see her sequel Judy's turn to cry. A much better song with a better message for teenagers is her You don't own me.)
CLYDE: Oh well. However, I'll make sure to tell that example to my class.
(ADDED LATER: Quanta had a nice article on non-primrec functions recently here. The problem they are talking about is discussed in the comments.)
