Type 3 functions

Let \(A\) be a recursive set. Let \(f\) be a function that terminates for \(x\) if \(x\) belongs to \(A.\) If \(x\) is not in \(A,\) then \(f(x)\) evaluates to \(f(x + 1),\) then \(f(x + 2),\) and so on, until it gets to \(f(y),\) where \(y\) is in \(A.\) Call functions which satisfy these properties type 3. A type 3 function always terminates, because for every \(x,\) there must be some \(y\) such that \(y \ge x,\) and \(y \in A.\) Because we're interested in termination, and not the values spit out by a function, we can omit the roots of each termination path from the call graph. This helps us focus on the more important structure in each call graph. Here's the call graph of a type 3 function, where \(A\) is the set of all powers of 2: