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 'A variant of the Monty Hall problem'

There is a nice little variation of the problem. The host says, after you have chosen the door, that you can change your guess, but to sweeten the deal, he says you can choose the two other doors, if you wish. This proposition is a no brainer, however before you are quick enough to accept it, the host opens one of the two doors and it is empty. In this version you really want to change your pick, but at the same time ask yourself is the host impartial and does that change anything. The host...
View full post »

Similar threads

MHB Recursive and Primitive recursive functions
  • · Replies 5 ·
Replies
5
Views
3K
I 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
I 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
I Questions Regarding Primitive Unit Cell
  • · Replies 4 ·
Replies
4
Views
4K