My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Thanks Tree1Thanks
  • 1 Post By Evgeny.Makarov
Reply
 
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.
safyras is offline  
 
May 10th, 2014, 06:40 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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?
CRGreathouse is offline  
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.
safyras is offline  
May 11th, 2014, 11:53 AM   #4
Member
 
Joined: Jul 2010

Posts: 95
Thanks: 0

Could anyone explain?
safyras is offline  
May 11th, 2014, 11:59 AM   #5
Senior Member
 
Joined: Dec 2013
From: Russia

Posts: 327
Thanks: 108

Quote:
Originally Posted by safyras View Post
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.
Thanks from safyras
Evgeny.Makarov is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

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 hyper-operators/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





Copyright © 2019 My Math Forum. All rights reserved.