Where do non-primitive recursive functions come up naturally?
blog.computationalcomplexity.org
blog.computationalcomplexity.org
I like the lexicographic descent criterion as a not too contrived example of a class of programs larger than primitive recursion, and yet for which it's easy to prove termination (e.g., https://goto.ucsd.edu/~gridaphobe/liquid/haskell/blog/blog/2...). That's apparently equivalent to the class of multiply-recursive functions (https://dl.acm.org/doi/abs/10.5555/860256.860258)
Any computable function whose running time grows slower than that, i.e. bounded by some f_k for finite k, should be primitive recursive, since one can just add f_k(n) upper bounds to any unbounded loop without affecting the result.
I think functions growing as fast as Ackermann's don't come up naturally, except on a Googology forum.
> 6) QUESTION: We know that GO and CHESS have very high complexity, but are still 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?
I've used the union-find data structure for keeping track of groups of connected stones in Go. And also for keeping track of connected cells for generating random mazes.
Apparently I spoke too soon. One problem where Ackermann naturally comes up is the Vector Addition Systems [1] just discussed today.
Agda programming language (which requires halting, and therefore is not Turing-Complete) has a robust coinduction support. E.g. in this [1] tutorial you can see it being used to construct decidable languages. A more traditional tutorial to coinduction could be found here [2].
[0] if we count primitive corecursion as "non-primitive recursive" here
[1] https://agda.readthedocs.io/en/v2.6.4.1/language/sized-types...
[2] https://agda.readthedocs.io/en/v2.6.4.1/language/coinduction...
``` function fWhile(q){ doSomethingWith(q.pop()) return !q.empty ? fWhile(q) : void }
fWhile(queue)
```
- edit I think I see what you are saying, I must not really understand the concept of primitive recursion (or non-, not sure which I don't understand)
while(true){
}
f=()=>f()
F is recursive. While is iterative.
An iterative process can be recursive or not.
And once you look at procedures that use two stacks, like this[1], then it becomes pretty apparent just how arbitrary the distinction is.
I mean that anything iterative looks to me like a simple (linear) case of recursion. But I can imagine a series of calls that is recursive but not linearly iterative.
Unfortunately some "poorly designed language implementations"[0] will fail to run such functions, with the "stack overflow" you mention.
[0] https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO
Primitive recursion is equivalent to a 'for' loop with a pre-computed bound, e.g. 'for i in [0..X]: ...'.
Recursion that's "non-primitive" would include general recursion, which places no restriction on how we recurse; e.g. we could recurse on the next state of a Turing Machine. General recursion is equivalent to a 'while' loop which re-computes its condition after each iteration.
"Non-primitive" recursion can also include other restricted forms of recursion, which do not allow general computation, but cannot be represented by a primitive-recursive form; for example, the (usual definition of the) Ackermann function mentioned in the article takes two arguments, and its recursive calls can increase the second argument (so it's not primitive recursive). However, the pair of arguments always decrease according to (x, y) < (x, y+1) (if the first argument stays the same, the second argument must decrease) and (x, y) < (x+1, z) (if the first argument decreases, we can use anything for the second argument). The latter condition is so permissive that the Ackermann function is allowed to recurse with a second argument that is itself the result of another recursive call. This grows so fast that the number of loop iterations required to implement it cannot be computed by a primitive-recursive function (whatever function we try, there will eventually be an input that requires more iterations than that function returns).
If we're allowing unbounded (co)datastructures then a singly-linked list will do the trick.
Perhaps these examples don't count since they're not computable functions. Specifically, searching for an element in a bottomless tree/list that doesn't contain it will not halt, making this a partial function.
One challenge I found is that I have to set the upper bounds conservatively. For example for sqrt(n), the loop actually counts all the way up to n, because in the worst case, sqrt(1) = 1. As another example, to find the nth prime number, I search up to 2^n, because a conservative lower bound is that there is at least one prime number between 2 and 4, between 4 and 8, between 8 and 16, etc.
Yes. Often one can (after much thought and code) write something that explicitly reduces a problem in just* the right order, but it is quicker and simpler to repeatedly apply a set of rewrites WHILE any changes have been made.
* see Knuth on Tarjan's SCC
while not stream.closed:
symbols = []
current_symbol = None
while not current_symbol == END:
current_symbol = stream.read()
symbols.append(current_symbol)
# Do stuff with symbols.
In English, when you say while A, B" it means "as long as condition A is fulfilled, condition B is also fulfilled". Like "while the window is open, the room is getting colder".
But then in programming, that's not how it works. "while the stream is not closed..." what? A variable called symbols is being assigned. That's an action - so how often does it happen? Once or multiple times? Can the code after the while run in parallel or only sequential? And don't even get me started with forgetting to close the stream.
Etc. etc.
Intuitively it would be: "1.) open a stream. 2.) If there is nothing more to read, close the stream, otherwise read one symbol and add it to the list of symbols. Repeat 3.) repeat step 2".
So for me at least, the recursive version is much more intuitive. it's how I think about it and how I would think about it if it were a real-world problem too.
Now it's a bit confusing if you're used to other languages, because you might think "while" is a test-at-start and "Until" is test-at-end, but actually while and until can both be tested either at the start or the end, and While and Until are just testing the negation of each other.
It can also be extra confusing, because there is a separate While.. End loop without the Do that can be used instead.
There's a reason Visual Basic died out, and it isn't just the snobbishness of seeing C# as more of a "real" language.
> But then in programming, that's not how it works. "while the stream is not closed..." what? A variable called symbols is being assigned. That's an action - so how often does it happen? Once or multiple times? Can the code be after the while run in parallel or only sequential? And don't even get me started with forgetting to close the stream
Ruby has the "until" keyword as an alternative to "while not" (similar to but not as commonly needed as "unless" for "if not"). I've honestly always kind of liked Ruby's willingness to go out of its way to try to make things like this more natural, but sadly I think I'm in the minority on this one.
The one that always feels the most funky to me is whenever I have to invert `is_empty` in some way; I wish that languages would standardize having a method that means the opposite purely for aesthetic reasons, which I suspect would be wildly unpopular with everyone else besides me due to being seen as "redundant".
For example, wiping one's butt:
do {
wipe()
} while { color_of_tp() !== "white" }
Although I'd argue while loops belong most at home in imperative code. (Cleaning for example is like the impure function par excellence, done only for side effect)
Some people were once trying to come up with the most useless possible superhero or supervillain, and I suggested "Exact Wipe Man", with the power to look at the result of a wipe of anything and know if that was the last wipe needed.
While on the subject of wiping one's derrière, I once read a question in an advice column where the questioner said that for some reason that subject came up among a group of people and someone asked what direction people wipe. It turned out that in that group of around 10 people 9 went one way and one went the other. That one wrote to ask if he was a freak or if he was normal and surrounded by freaks.
The columnist of course had no idea what the answer was, and asked around the office. She found that nearly everyone in the office went the same way as the questioner's friends, and informed him that he did appear to be unusual.
It turns out that I am also in the minority group. It had never even occurred to me that anyone might go the other way as it seems completely unnatural to me. Most people wipe in private with not even people they are in intimate physical relationships with watching and it is almost never a topic of discussion so you can be doing it completely different from everyone else and never find out.
This raises the question of what other things do we regularly do in private but might be doing in some way different from most other people? Maybe I'm flossing or brushing my teeth in some weird way, or maybe the way I turn on under the shower head always misses one particular spot and so I've got some section in the middle of my back that's never washed, or something like that?
I was tempted to subscribe to a month or two of one of those "voyeur" sites where they have a house with cameras in every room so you can see everything the residents do, to see how my flossing, showering, etc., compared, but never got around to doing so.
The flossing and teeth brushing thing, though, seriously? I don't know in principle if I'm doing it the same as other people, but I do remember quite well my parents teaching me to do it and I at least do it the same way they do. I didn't just figure out how to brush my teeth as a 3 year-old by trial and error. It was a topic of discussion at one point, at least with them, and that presumably means I do it the same way as my sisters.
True! Although I'd argue that's just part of the human condition. How do we check if any given condition obtains? Very often the simplest and most effective approach is just to perform some action which depends on that condition for its success, and we conclude from the fact that our action succeeded/failed that the condition does/doesn't obtain. How do we check if a closed door is locked? Technically we could use a see-through camera to observe the lock mechanism, but it's more straightforward to just try to push it open and see if we succeed/fail to do so. Ideally we may prefer structured decision-making like if-else and switch-case statements but in reality we tend to go for the quick and dirty (if less elegant, and sometimes wasteful) try-catches. :)