Primitive recursive functions :mad:

In summary, to show that the set A is primitive recursive, we need to show that its characteristic function χ(n) is primitive recursive. The characteristic function can be defined as 1 if for all m less than n, the value of f(m) is not equal to f(n), and 0 if there exists an m less than n where f(m) is equal to f(n). However, an algorithm for computing this characteristic function is needed.
  • #1
novawildcat
1
0
Let f be a primitive recursive total function, and let A be the set of all n such that the value f(n) is 'new' in the sense of being different from f(m) for all m<n. Show that A is primitive recursive.


How in the world do I attack this problem? I am totally lost. Any help would be greatly appreciated. Thanks.


I know that to show a set is primitive recursive the characteristic function of the set must be primitive recursive. What in the world, however, would be a suitable characteristic function for this set described above?
 
Physics news on Phys.org
  • #2
What in the world, however, would be a suitable characteristic function for this set described above?

[tex]
\chi (n) := \left\{
\begin{array}{ll}
1 \quad & \forall m < n: f(m) \neq f(n) \\
0 & \exists m < n: f(m) = f(n)
\end{array}
[/tex]

Sounds good, I think.

I think the better question to ask, though, is an algorithm for actually computing &chi;(n)... it doesn't even have to be a good algorithm, just an algorithm.
 
  • #3



Don't worry, tackling this problem can seem daunting at first but with some guidance, you'll be able to understand it better. First, let's break down the problem into smaller parts.

1. Understanding Primitive Recursive Functions:
Primitive recursive functions are a subset of recursive functions, which are functions that can be computed by a Turing machine. These functions have the following properties:
- They are defined for all natural numbers (0, 1, 2, etc.)
- They can be computed using a finite number of basic operations such as addition, multiplication, and composition (applying one function to the output of another)
- They have a well-defined recursion rule, meaning the value of the function at a given input is defined in terms of its value at smaller inputs.

2. Understanding the Given Function:
Let's break down the given function f(n) and the set A to better understand them:
- f(n) is a primitive recursive total function, meaning it is defined for all natural numbers and can be computed using a finite number of basic operations.
- A is the set of all n such that the value f(n) is 'new', meaning it is different from the value of f(m) for all m < n. In other words, A consists of all the inputs that result in a different output for f(n).

3. Showing A is Primitive Recursive:
To show that A is primitive recursive, we need to show that its characteristic function (the function that returns 1 if an input is in the set and 0 if it is not) is also primitive recursive. We can do this by using the well-defined recursion rule of primitive recursive functions.

First, we define a new function g(n) that returns 1 if n is in A and 0 if it is not. We can define g(n) recursively as follows:
- g(0) = 0 (since 0 is not in A)
- g(n+1) = 1 if f(n+1) is 'new' (meaning it is different from all previous values of f) and 0 otherwise.

Now, we can use the well-defined recursion rule of primitive recursive functions to define g(n). We know that f(n) is a primitive recursive function, so we can define g(n) in terms of f(n) as follows:
- g(0) = 0
- g(n+1) = 1 - h(n) * f(n+1
 

Related to Primitive recursive functions :mad:

1. What are primitive recursive functions?

Primitive recursive functions are a type of mathematical function that can be computed using a specific set of rules. These functions are used in the field of computability theory to study the limits of what can be computed by a computer.

2. How are primitive recursive functions different from other types of functions?

Primitive recursive functions are different from other types of functions in that they are limited in their ability to compute complex or non-terminating functions. They are defined by a set of basic operations, such as addition and multiplication, and are only able to compute functions that can be expressed in terms of these basic operations.

3. What are the applications of primitive recursive functions?

Primitive recursive functions are primarily used in the field of computability theory to study the limits of computation. They are also used in other areas of mathematics, such as set theory and logic, to prove theorems and solve problems.

4. Can all functions be expressed as primitive recursive functions?

No, not all functions can be expressed as primitive recursive functions. There are some functions that are not computable by any algorithm, and therefore cannot be expressed as primitive recursive functions.

5. What are some examples of primitive recursive functions?

Some examples of primitive recursive functions include addition, multiplication, exponentiation, and factorial. These functions can be expressed using the basic operations and rules of primitive recursive functions.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
5K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
18
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top