
Linear Algebra Linear Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 10th, 2014, 06:29 AM  #1 
Member Joined: Jul 2010 Posts: 95 Thanks: 0  Ackermann function and primitive recursive functions
Hello, I see everywhere written that Ackermann function is not primitive recursive function, because it grows faster than primitive recursive functions. I can't get the idea what was meant by saying grows faster than primitive. So, can anyone explain step by step what it means that Ackermann function is not primitive recursive? Thanks. 
May 10th, 2014, 06:40 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
What is the definition you learned for primitive recursive?

May 10th, 2014, 07:33 AM  #3 
Member Joined: Jul 2010 Posts: 95 Thanks: 0 
Functions which can be obtain from base functions (zero function, successor function, projection function ) using only composition operator and primitive recursion operator are called primitive recursive function.

May 11th, 2014, 11:53 AM  #4 
Member Joined: Jul 2010 Posts: 95 Thanks: 0 
Could anyone explain?

May 11th, 2014, 11:59 AM  #5 
Senior Member Joined: Dec 2013 From: Russia Posts: 327 Thanks: 108  From what I remember, this means that for every primitive recursive function $f$ there exists a number $m$ such that the function $n\mapsto A(m,n)$ grows faster than $f$. It's enough to show that $f(n)<A(m,n)$ for some $n$. Proving this fact carefully requires a bit of work.


Tags 
ackermann, function, functions, primitive, recursive 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help on Recursive Functions?  loveinla  Algebra  0  March 12th, 2013 10:55 AM 
Primitive Recursive Function  sdj  Computer Science  2  October 24th, 2012 05:39 AM 
Ackermann's function A (2,2)  mathproblems  Applied Math  0  December 4th, 2011 10:18 AM 
solution to complex hyperoperators/Ackermann function  jamesuminator  Number Theory  5  June 25th, 2011 12:16 PM 
Ackermann's Function  aikiart  Computer Science  6  August 26th, 2010 11:50 AM 