My Math Forum Ackermann function and primitive recursive functions

 Linear Algebra Linear Algebra Math Forum

 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

Quote:
 Originally Posted by safyras I see everywhere written that Ackermann function is not primitive recursive function, because it grows faster than primitive recursive functions.
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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post loveinla Algebra 0 March 12th, 2013 10:55 AM sdj Computer Science 2 October 24th, 2012 05:39 AM mathproblems Applied Math 0 December 4th, 2011 10:18 AM jamesuminator Number Theory 5 June 25th, 2011 12:16 PM aikiart Computer Science 6 August 26th, 2010 11:50 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top