7
$\begingroup$

I'm not sure if my wording is entirely correct, but I was just wondering if every recursive formula can be turned into an explicit formula.

I am asking this because various sources online gives me opposite answers. Although, one thing I have noticed is that every source likes to use different words other than "formula", like "expression" and such.

According to wiki, "Although not all recursive functions have an explicit solution"

So I guess another part of my question is : What difference is it when people say recursive function, expression, formula, etc. (if there is any)

But yeah, I have seen a stackoverflow post saying that every recursion can be turned into an iteration, and doesn't this also mean everything can be explicitly defined?

  • 0
    Define $f(0)=1$ and $f(n)=n f(n-1)$, for $n \geq 1$. Thus $f(n)=n!$. Is this "explicit"? It's a matter of opinion: some people say no, others say yes.2012-10-18
  • 0
    I think you need to fix a language of terms in order to get a meaningful answer. Anyways, are we allowed to use [Iverson brackets](http://en.wikipedia.org/wiki/Iverson_bracket), $\sum$ and $\prod$ symbols, for the non-recursive expression?2012-10-19
  • 0
    I'm not sure if I understand how this can be an opinion. Shouldn't this just be true or false? Or do people define recursion differently? As for summations, I thought that summation indicates recursion. And I never saw the other symbol before.2012-10-19
  • 0
    @krikara What is your definition of "explicit formula"?2012-10-19
  • 0
    I'm thinking of recursive as a formula that depends on the previous value to obtain the next whereas an explicit one does not depend on any previous values. Not sure if this is correct, but this is how I came to understand recursion2012-10-19
  • 0
    @krikara That sounds reasonable, but it does not sound like a formal definition, so I'm not sure if the question has a correct answer.2012-10-19
  • 0
    Can the function which maps $n$ to the number of steps required for the Goodstein sequence of $n$ to terminate (see https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Application_to_computable_functions) be given "explicitly"? It grows very fast, and the fact that it is a total function cannot be proved in Peano Arithmetic.2012-10-19

2 Answers 2