MHB Can We Enumerate All Primitive Recursive Functions?

Click For Summary
Primitive recursive functions can be enumerated by listing all possible derivations and definitions. This enumeration is relevant in demonstrating that Ackermann's function is not primitive recursive. The proof of Ackermann's non-primitive recursive status involves showing properties applicable to all primitive recursive functions through this enumeration. The discussion clarifies that enumeration includes all basic functions and their definitions through compositions or primitive recursions. Understanding this enumeration is crucial for exploring the boundaries of primitive recursive functions.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

Can we enumerate the primitive recursive functions?
 
Physics news on Phys.org
Of course, just enumerate all possible derivations (definitions).
 
Is the enumeration of primitve recursive functions an other way to show that Ackermann's function is not primitive recursive? Or isn't it possible?
 
In the proof that Ackermann's function is not p.r. you prove something for all p.r. functions, and you do this by enumerating all possible derivations.
 
Evgeny.Makarov said:
In the proof that Ackermann's function is not p.r. you prove something for all p.r. functions, and you do this by enumerating all possible derivations.

By "enumerating all possible derivations" do you mean that we enumerate all possible cases how the p.r. function is defined, if it is one of the basic functions (constant, successor, projection), or is defined by compositions or primitive recursions?
 
Yes.
 

Thread 'Two interesting number theory tricks'

First trick I learned this one a long time ago and have used it to entertain and amuse young kids. Ask your friend to write down a three-digit number without showing it to you. Then ask him or her to rearrange the digits to form a new three-digit number. After that, write whichever is the larger number above the other number, and then subtract the smaller from the larger, making sure that you don't see any of the numbers. Then ask the young "victim" to tell you any two of the digits of the...
View full post »

Similar threads

MHB Recursive and Primitive recursive functions
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Is the Inverse Image of a Computable Function Recursively Enumerable?
  • · Replies 3 ·
Replies
3
Views
2K
MHB Propositions for recursive functions
  • · Replies 18 ·
Replies
18
Views
4K
MHB Primitive recursive functions/sets
  • · Replies 6 ·
Replies
6
Views
2K
MHB Showing the nth prime is primitive recursive
  • · Replies 1 ·
Replies
1
Views
5K
There are effectively computable numerical functions which aren’t prim
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Explaining Enumerable: Understanding the Concept in Godel, Escher, Bach
  • · Replies 6 ·
Replies
6
Views
2K
MHB Points about the Ackermann's function
  • · Replies 16 ·
Replies
16
Views
4K
MHB Ackermann's function is μ-recursive
  • · Replies 11 ·
Replies
11
Views
4K
Undergrad Questions Regarding Primitive Unit Cell
  • · Replies 4 ·
Replies
4
Views
4K