4 added 52 characters in body

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 make 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!

3 added 1604 characters in body

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 make 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? Can you be more specific about this? Thanks!

2 edited tags
1