Primitive recursive functions :mad:

[novawildcat]

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?

 

[Hurkyl]

What in the world, however, would be a suitable characteristic function for this set described above?

$$\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}$$

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.

 

[tacman]

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