Can We Enumerate All Primitive Recursive Functions?

In summary, the conversation discusses enumerating primitive recursive functions and how it can be used to prove that Ackermann's function is not primitive recursive. The process involves enumerating all possible derivations of p.r. functions and considering their definitions.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

Can we enumerate the primitive recursive functions?
 
Physics news on Phys.org
  • #2
Of course, just enumerate all possible derivations (definitions).
 
  • #3
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?
 
  • #4
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.
 
  • #5
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?
 
  • #6
Yes.
 

FAQ: Can We Enumerate All Primitive Recursive Functions?

What are primitive recursive functions?

Primitive recursive functions are a type of mathematical function that can be defined using basic operations such as addition, multiplication, and composition. They are often used in theoretical computer science and are important for analyzing the complexity of algorithms.

What is the difference between primitive recursive functions and general recursive functions?

The main difference between primitive recursive functions and general recursive functions is that primitive recursive functions are guaranteed to terminate, while general recursive functions may not. This means that primitive recursive functions are a subset of general recursive functions.

Can all computable functions be expressed as primitive recursive functions?

No, not all computable functions can be expressed as primitive recursive functions. There are some computable functions that require more complex operations, such as unbounded search or minimization, which cannot be expressed using only primitive recursive functions.

What is the importance of primitive recursive functions in theoretical computer science?

Primitive recursive functions are important in theoretical computer science because they help us understand the complexity of algorithms. By analyzing the primitive recursive complexity of an algorithm, we can determine its efficiency and make improvements to optimize its performance.

How are primitive recursive functions used in practical applications?

While primitive recursive functions are primarily used in theoretical computer science, they can also be applied in practical applications such as program verification and proof of correctness. They are also used in some programming languages, such as Haskell, to define and manipulate mathematical structures.

Similar threads

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

Hot Threads

Recent Insights

Back
Top