Prove a function is primitive recursive - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T12:06:38Z http://mathoverflow.net/feeds/question/16913 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16913/prove-a-function-is-primitive-recursive Prove a function is primitive recursive Peter Marsh 2010-03-02T20:26:21Z 2010-03-31T19:07:31Z <p>Hey,</p> <p>I'm taking a course in computability theory, but I'm struggling with primitive recursion. More specifically we are often asked to prove that some arbitrary function is primitive recursive, but I really don't know how to go about doing so.</p> <p>For example:</p> <p>Let $\pi (x)$ be the number of primes that are $\le x$. Show that $\pi (x)$ is primitive recursive.</p> <p>How do you go about proving this formally? And, in general, what are the necessary conditions to prove if something is or is not primitive recursive.</p> <p>Note: this isn't homework, I've pulled the question out from a list of examples we have been given :)</p> http://mathoverflow.net/questions/16913/prove-a-function-is-primitive-recursive/16915#16915 Answer by Mariano Suárez-Alvarez for Prove a function is primitive recursive Mariano Suárez-Alvarez 2010-03-02T20:34:29Z 2010-03-02T20:45:00Z <p>Show that the function $$f(x)=\begin{cases}1,&amp;\text{if x is prime;}\\0,&amp;\text{otherwise}\end{cases}$$ is primitive recursive. </p> <p>Then show that given any primitive recursive function $f:\mathbb N\to\mathbb N$, the function $g:\mathbb N\to\mathbb N$ such that $g(x)=\sum_{y=1}^xf(y)$ is also primitive recursive. Then adapt this to prove what you want. </p> <p>In general, what you do to prove that a specific function is primitive recursive depends on the function---unsurprisingly. I'd love to hear about non-trivial sufficient conditions of a general nature, though...</p> <p>There are, on the other hand, various necessary conditions for a function to be primitive recursive, which can be used to show that specific functions are <em>not</em> primitive recursive. This is how one shows, for example, that the Ackermann function is not primitive recursive: one shows that it grows too fast.</p> http://mathoverflow.net/questions/16913/prove-a-function-is-primitive-recursive/16927#16927 Answer by Andrej Bauer for Prove a function is primitive recursive Andrej Bauer 2010-03-02T22:07:06Z 2010-03-02T23:34:32Z <p>This is not an exact answer, but it helps to quickly determine in many cases that a given function is primitive recursive. The idea is to use a reasonable programming language in which your function can be expressed more easily than with "raw" arithmetic and primitive recursion. Of course, the programming language must be limited enough to prevent unbounded searches and other constructs that lead to general recursion. I mention here just one easy possibility.</p> <p>Suppose a function $f : \mathbb{N} \to \mathbb{N}$ is computed by a simple imperative program in polynomial running time (actually, as Grigory points out in his answer, any primitive recursive bound will do). More precisely, the program is allowed to use basic arithmetic operations, boolean values, variables, arrays, loops, and conditional statements. Then the function $f$ is primitive recursive.</p> <p>The reason that such a program can only define a primitive recursive function is that the entire execution of the program may be encoded by a number $N$ whose bit size is bounded by a polynomial $p(n)$, where $n$ is the input. Because verifying that a number encodes the execution of a simple imperative program is primitive recursive, we can perform a bounded search up to $2^{p(n)}$ to find the number $N$ (such a bounded search is primitive recursive) and extract the answer from it.</p> <p>Let us apply this to your question. The following Python program computes the function $\pi(n)$ and uses just a couple of loops and basic arithmetic (we could replace the remainder function % with another loop). Its running time is quadratic in $n$, assuming all basic operations are constant time:</p> <pre><code>def pi(n): '''Computes the number of primes which are less than or equal n.''' p = 0 # the number of primes found k = 2 # for each k we test whether it is prime while k &lt;= n: j = 1 # possible divisors of k d = 0 # number of divisors of k found while j &lt;= n: if k % j == 0: d = d + 1 j = j + 1 if d == 2: p = p + 1 k = k + 1 return p </code></pre> <p>Therefore your function is primitive recursive.</p> http://mathoverflow.net/questions/16913/prove-a-function-is-primitive-recursive/16932#16932 Answer by Grigory Yaroslavtsev for Prove a function is primitive recursive Grigory Yaroslavtsev 2010-03-02T22:41:55Z 2010-03-02T22:58:22Z <p>There is a theorem that says that any function computable on a Turing machine in time that is a primitive recursive function of the length of the input is primitively recursive.</p> <p>This theorem you can find here: <a href="http://en.wikipedia.org/wiki/Primitive_recursive_function" rel="nofollow">http://en.wikipedia.org/wiki/Primitive_recursive_function</a></p> <p>Your function is primitively recursive because it can be computed in $O(n^2)$ time (here $n$ is the length of the input) on a computer using some programming language like C++. The difference between the time needed to implement this algorithm in C++ and on a Turing machine is polynomial in the length of the input so the resulting time needed for implementation on a Turing machine is polynomial in $n$.</p> <p> Proving that function is not primitive recursive is harder. There is a proof with diagonalization method that shows that there exists some not primitively recursive function. To construct some explicit function it can be noted that if function grows too fast than it is not primitively recursive. Ackerman's function has the right growth rate for this. </p> http://mathoverflow.net/questions/16913/prove-a-function-is-primitive-recursive/16938#16938 Answer by Dan Piponi for Prove a function is primitive recursive Dan Piponi 2010-03-02T23:52:52Z 2010-03-02T23:52:52Z <p>A conceptually simple test for whether a function is primitive recursive is whether or not you can write it in <a href="http://en.wikipedia.org/wiki/BlooP_and_FlooP" rel="nofollow">Bloop</a>.</p> <p>The crucial point is that the loop control flow structure forces you to say in advance how many times it will loop.</p> <p><a href="http://c2.com/cgi/wiki?BloopFloopAndGloop" rel="nofollow">Here</a>'s some example code for working with primes written in Bloop.</p> http://mathoverflow.net/questions/16913/prove-a-function-is-primitive-recursive/19985#19985 Answer by Andreas Weiermann for Prove a function is primitive recursive Andreas Weiermann 2010-03-31T19:07:31Z 2010-03-31T19:07:31Z <p>There is a theorem that says that any function computable on a Turing machine in time that is a primitive recursive function of the length of the input is primitively recursive.</p> <p>This just mentioned result is a really powerful theorem with numerous applications.</p> <p>It easily yields results like this one.</p> <p>Assume g,h,p are prim rec. Then f is prim rec where</p> <p>f(x,y)=g(x,y) if x times y is 0 and f(x+1,y+1)=h(x,y,f(x,f(x,p(x,y))),f(x+1,y)).</p> <p>Trying to figure out "direct solutions" is more or less impossible.</p> <p>So my recommendation: If course of values recursion and simultaneous recursion don't work try the theorem above.</p>