5
$\begingroup$

Consider a function $w(i)$, $i \in \mathbb{N}$, defined recursively by:

$w(0)=w(1)=1$, and

$w(i)={i}^{n}-\sum_{j=1}^{i-1}{i \choose j}w(j)$ for $i>1$.

Is it possible to write $w(i)$ out explicitly as a function of $i$ (i.e., with only $i$ on the right hand side), for $i>1$ ?

In general, given a recursively defined total computable function say, $f(n)$, is it always possible, in principle, to write out $f(n)$ explicitly as a function of $n$, for $n$ large enough? I suspect it's impossible. If so, what is the real reason that prevents us from doing so?

Another well known example that comes to my mind is:

$f(0)=f(1)=c$, and

$f(i)=5f(i-1)(1-f(i-1))$

where we can choose some value of $c \in (0,1)$ so that the trajectory of $f(i)$ becomes chaotic in $(0,1)$. If we could really express any recursively defined total computable function explicitly, then we could write out the chaotic trajectory in a finite, flat and non-dynamic formula, which seems strange to me. (or can we?)


Edit: Thank you very much for all the answers. They are really helpful.

@Joel: Is the recursive formation essential when the resulting recursive function doesn't grow faster than it's component functions ${g}_{i}$ (in your notation)? i.e., is it true that given ${g}_{i}$ and recursive function $f$ defined on them, as long as $f$ doesn't grow faster than the fastest of ${g}_{i}$, the recursive formation can be dispensed with?

@Carl: By "...it is not possible to come up with a completely explicit form for every computable function, in some fixed signature" , did you mean to write out the functions symbolically using finite, fixed set of symbols? In @Joel's interpretation, he didn't distinguish between we being able to symbolically write out exponential functions as, say ${2}^{n}$, and just taking the recursive function on multiplication as another "known" basic function ${g}_{i}$. Of course, one may just dismiss ${2}^{n}$ as a "shorthand" for the whole recursive formation, but I do feel they are not quite the same ("${2}^{n}$" is closer to what I had in mind by "explicit". I'd like to know if the distinction makes any sense in any sense).

Another question I have concerns about this "...because then by enumerating all possible forms we would get a numbering ϕ as in the theorem" But just because we can write a completely explicit form for each computable function doesn't mean we can enumerate these forms effectively, does it? If we can't, this does not contradict the theorem. Can you be more specific about this? Thanks!

$\endgroup$
8
  • 4
    $\begingroup$ Define “write explicitly”. $\endgroup$ Dec 16, 2011 at 14:27
  • 1
    $\begingroup$ Define "math philosophy". $\endgroup$ Dec 16, 2011 at 16:30
  • 1
    $\begingroup$ @François: I’m not sure whether your comment was directed to the OP or to me, but here is one: en.wikipedia.org/wiki/Philosophy_of_mathematics . Specifically, the definition of math philosophy is not “anything that looks like mathematics, but is formulated too vaguely to be a rigorous mathematical question”, contrary to popular belief. $\endgroup$ Dec 16, 2011 at 16:53
  • 1
    $\begingroup$ In response to your @Joel: It is not the case that slow-growing functions can always be expressed without recursion. It is simply easier to prove that fast-growing functions cannot be so expressed. In response to your @Carl: I think that introducing a notation like $2^n$ and introducing a basic function like $Exp(2,n)$ is mathematically equivalent. We think of exponentiation as being explicit because we use it so often. $\endgroup$
    – Will Sawin
    Dec 20, 2011 at 0:06
  • 1
    $\begingroup$ In response to your final thing: If I give you a closed-form formula, you should be able to tell if it denotes a function, and what function it denotes. You can enumerate all formulas, by enumerating all strings of texting and crossing out the ones that aren't formulas for something. $\endgroup$
    – Will Sawin
    Dec 20, 2011 at 0:06

4 Answers 4

9
$\begingroup$

The class of primitive recursive functions is the smallest class of functions containing the basic primitive recursive functions (zero, successor, projection) and closed under the two operations:

  • composition: if $h$ and $g_1,\ldots,g_k$ are primitive recursive, so is the function $$\vec x\mapsto h(g_1(\vec x),g_2(\vec x),\ldots,g_k(\vec x)).$$
  • primitive recursion: if $h$ and $g$ are primitive recursive, then so is the function $f$ defined by $$f(0,\vec x)=h(\vec x),$$ $$f(n+1,\vec x)=g(n,\vec x, f(n,\vec x)).$$

This class is extremely robust and includes all of the functions that you mention in your question (but it falls short of the class of all Turing computable functions). I interpret your question as being about the extent to which we might hope to eliminate the recursion scheme, and still arrive at the same class of functions.

One easy observation, of course, is that we cannot simply eliminate the recursion scheme as is and still get all primitive recursive functions. For example, even if we add addition and multiplication as basic functions, then the composition scheme will remain inside the class of polynomial functions. But we can easily define the exponential function $n\mapsto 2^n$ by recursion over that class, and this does not have polynomial growth.

More generally, let us consider whether we might add finitely many additional, powerful primitive recursive functions $g_1,\ldots,g_k$ as basic, and then close only under composition. This interpretation of the question would be: can we arrange that this class is closed under definition by recursion? In other words, is every function definable by recursion using those functions and their compositions already expressible as a term in the language using only those functions (that is, as a composition)?

The answer to this more general version of the question is still no. For any finitely many primitive recursive functions $g_1,\ldots,g_k$, the closure of it under composition is strictly smaller than the closure of it under composition and definition by recursion. Specifically, there will be a primitive recursive function $f$, defined by one or more recursions over those $g_i$ and the usual basic functions, which has a higher growth rate than any individual term in those functions. This can be proved by using a high enough level function $A_n$ of the Ackermann function, because whenever a collection of functions is dominated by $A_n$, then all terms in those functions are dominated by $A_{n+1}$.

$\endgroup$
2
  • $\begingroup$ @Joel:Thank you. But more interestingly, can every "slow-growing" recursive function be expressed without recursion, as asked in my edit? According to Will's comment they can't. But is there an example of such? $\endgroup$
    – Eric
    Dec 21, 2011 at 1:53
  • 1
    $\begingroup$ No, that is too much. Sets can code a lot of information about fast-growing functions, but their characteristic functions are bounded and hence slow-growing. Thus, the use of fast growth in my answer was just an easy way to prove that the classes are different; but there should be no reason to expect that the smaller class has all the slow-growing or indeed, even all the bounded growth functions of the big class. $\endgroup$ Dec 21, 2011 at 2:09
7
$\begingroup$

With regard to the general question, I defer to Joel Hamkins's answer. For your specific function, though, the first few cases give

$$\begin{align} w(2) &= 2^n - 2 \\\ w(3) &= 3^n -3\cdot 2^n + 3\\\ w(4) &= 4^n - 4\cdot 3^n + 6\cdot 2^n - 4\\\ w(5) &= 5^n - 5\cdot 4^n + 10\cdot 3^n - 10\cdot 2^n + 5 \end{align}$$

This suggests the explicit formula (where by "explicit" I just mean that the function $w$ doesn't appear on the right hand side)

$$w(i) = \sum_{j=0}^{i-1} (-1)^j(i-j)^n{i \choose j}$$

which I suspect (without taking time to verify) can be proved by straightforward induction.

A minor additional note: The OP's second example does not have chaotic trajectories. Because the coefficient 5 is greater than 4, the typical trajectory quickly escapes the unit interval and henceforth heads for $-\infty$.

Added 12/19/11: An elementary mathoverflow question that was opened and closed yesterday made me realize there's an interpretation for the function $w(i)$ that makes it easy to see the equivalence of the OP's recursive formula and the "explicit" formula I came up with: The function $w$ counts the number of maps from a set of $n$ objects onto a set of $i$ objects (with $n$ assumed greater than or equal to $i$). The OP's recursive formula does the count by starting with the number of all maps ($i^n$) and subtracting the number that are mappings onto subsets of size $j$ for $j=1$ to $i-1$. My explicit formula is an inclusion-exclusion count of all maps (not necessarily onto) from a set of size $n$ to sets of size $i-j$. The only little mystery from this point of view is why the equivalence works for all $n$, not just $n\ge i$.

$\endgroup$
7
  • 3
    $\begingroup$ In terms of the Stirling numbers of the second kind $S(n,i)$, we have $w(i) = i!\, S(n,i)$. $\endgroup$
    – Ira Gessel
    Dec 16, 2011 at 16:53
  • $\begingroup$ Asaf, thank you for aligning the displayed equations (although I kind of liked the original Christmas-tree tiering -- it seemed seasonally festive). $\endgroup$ Dec 16, 2011 at 18:05
  • $\begingroup$ :-)${}{}{}{}{}$ $\endgroup$
    – Asaf Karagila
    Dec 16, 2011 at 18:14
  • $\begingroup$ @Barry: Yes you are right about the 2nd example. The set $S$ of points that never leave (0,1) is measure zero, closed and perfect. The function is chaotic on this set $S$, not (0,1) itself. But if we are focusing on functions from integers to integers, this fact may not be very relevant :-( $\endgroup$
    – Eric
    Dec 18, 2011 at 15:28
  • $\begingroup$ @Barry: Actually I used the same mapping model inside my mind to come up with the recursive formula. Notice that $w(i)=0$ for $n<i$, consistent with this interpretation, too! (There's $0$ ways you can map $n$ objects onto $i$ objects if $n<i$). Alternatively you can model formulas as rolling a die $n$ times to come up with $i$ different numbers. If $n<i$, there's no way you can achieve it. $\endgroup$
    – Eric
    Dec 20, 2011 at 5:42
5
$\begingroup$

To follow up on Joel Hamkins' answer, the fundamental obstruction here is totality. Explicit definitions are always going to give total functions. The reason that recursion is so powerful for defining functions is that it is possible to make partial functions, e.g. $$ f(0) := 0 \qquad f(2n+2) := f(2n) \qquad f(2n+1) := f(2n+3) $$

The following is a standard theorem.

Theorem. Let $C$ be a countable system of total computable functions $\mathbb{N} \to \mathbb{N}$ with the property

  • There is a numbering $\phi_i\colon \mathbb{N} \to C$ such that every $f \in C$ is of the form $\phi_i$ for at least one $i$, and there is a uniform way to compute $\phi_i(j)$ given just $i$ and $j$.

Then $C$ does not include all total computable functions from $\mathbb{N}$ to $\mathbb{N}$.

Proof. Diagonalization.

In the context of this question, the philosophical meaning of this theorem is that it is not possible to come up with a completely explicit form for every computable function, in some fixed signature, because then by enumerating all possible forms we would get a numbering $\phi$ as in the theorem.

The closest we can hope for in terms of an explicit form for all total computable functions is something like Kleene normal form, but this still includes an unbounded search. Kleene's normal form theorem says that there is a primitive recursive function $U$ and a primitive recursive relation $T$ such that for every computable function $f$ there is an $e$ such that for all $i$, $$ f(i) \simeq U(\mu s . T(e,i,s)). $$ where $\mu$ is the unbounded search operator.

$\endgroup$
5
$\begingroup$

There is an easy inversion formula for $$a(k)=\sum_{j=0}^k\Big({k\atop j}\Big)b(j)\, ,$$ namely, $$b(k)=\sum_{j=0}^k (-1)^{k-j}\Big({k\atop j}\Big)a(j)\, ,$$ and in your case ($a(k):=k^n$) this produce the formula shown by Barry. You can see and prove it in several ways: The inverse matrix of the triangular matrix whose entries are the binomial coefficients. Or an identity between suitable generating functions. Also, as an instance of the inclusion-exclusion formula. I'm quite sure you may find nice hints in Concrete Mathematics by Graham, Knuth, and Patashnik.

$\endgroup$
1
  • $\begingroup$ Pietro, thanks, you're right, I probably should have extended my sum to run all the way to $j=i$. On the other hand, it's not clear how to interpret $0^n$ if $n=0$. Note the OP's sum never uses $w(0)$. $\endgroup$ Dec 16, 2011 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.