Using primitive recursion scheme

• Mar 19th 2010, 03:13 AM
Jagger
Using primitive recursion scheme
Hi!
I have to define the scheme of primitive recursion of this function:

$\displaystyle remove_from_left: \Sigma^{*}\mbox{x}\mathbb{N} \rightarrow \Sigma^{*}$

Some examples:
$\displaystyle removefromleft(abcdc,7)=\epsilon$

$\displaystyle removefromleft(abcdc,3)=dc$

First I gave a inductive definition for $\displaystyle \Sigma^{*}\mbox{x}\mathbb{N}$ then $\displaystyle \Sigma^{*}\mbox{x}\mathbb{N}$ is defined inductively by the next rules:

$\displaystyle (i) (\epsilon,0)\in\Sigma^{*}\mbox{x}\mathbb(N)$

$\displaystyle (ii) \mbox{ If } (w,0)\in\Sigma^{*}\mbox{x}\mathbb{N} and \mbox{x}\in\Sigma \Rightarrow (xw,0)\Sigma^{*}\mbox{x}\mathbb{N}$

$\displaystyle (iii)\mbox{ If } (w,n) \in \Sigma^{*}\mbox{x}\mathbb{N} \Rightarrow (w, n+1)\in\Sigma^{*}\mbox{x}\mathbb{N}$

After that I defined the scheme of primitive recursion for $\displaystyle \Sigma^{*}\mbox{x}N:$:

$\displaystyle \displaystyle \mathbb{H}$ Be $\displaystyle \Sigma^{*}$ a set and be :

-$\displaystyle f_0 \in \Sigma^{*}$

-$\displaystyle f_1:\Sigma^{*}\mbox{x} \mathbb{N} \mbox{x}\Sigma \mbox{x}\Sigma^{*}\rightarrow \Sigma^{*}$

-$\displaystyle f_2:\Sigma^{*}\mbox{x} \mathbb{N}\mbox{x}\Sigma^{*}\rightarrow \Sigma^{*}$

$\displaystyle \mathbb{T}$ Then exist only one function $\displaystyle removefromleft:\Sigma^{*}\mbox{x}\mathbb{N}\righta rrow\Sigma^{*}$ that:

$\displaystyle (i) removefromleft((\epsilon,0))=f_0=\epsilon$

$\displaystyle (ii) removefromleft((xw,0))=f_1((w,0),x,removefromleft( w,0))= xw$

$\displaystyle (iii) removefromleft((w,n+1))=f_2((w,n)$
$\displaystyle ,removefromleft(w,n))=removefromleft(w,n)$

Is this ok? Perhaps I have to change something...

Thank's!

Sorry for my bad english because I speak spanish(Worried)
• Mar 19th 2010, 06:26 AM
emakarov
When you write ... = removefromleft(w), where is the second argument? Also, it is not clear how w changes from one recursive call to the next in (iii).

Maybe it is easier to give inductive definitions for $\displaystyle \Sigma^*$ and $\displaystyle \mathbb{N}$ separately. Then you can define a helper function by primitive recursion that removes the left character from a word. Then you define the main function by recursion on the second (i.e., numerical) argument; it repeatedly removes the left character.
• Mar 19th 2010, 07:06 AM
Jagger
Thank's for the answer, I fixed the point you told me but I don't understand how to do what you say(Worried)
• Mar 19th 2010, 12:27 PM
emakarov
Quote:

Maybe it is easier to give inductive definitions for http://www.mathhelpforum.com/math-he...a80593e2-1.gif and http://www.mathhelpforum.com/math-he...c0743fcd-1.gif separately.
For $\displaystyle \mathbb{N}$:

$\displaystyle 0\in\mathbb{N}$
$\displaystyle n\in\mathbb{N}\Rightarrow S(n)\in\mathbb{N}$

Here $\displaystyle S$ is the successor function. Thus, $\displaystyle \mathbb{N}$ consists of terms $\displaystyle S(S(\dots S(0)\dots))$.

For $\displaystyle \Sigma^*$:

$\displaystyle \epsilon\in\Sigma^*$
for all $\displaystyle x\in\Sigma$, $\displaystyle w\in\Sigma^*\Rightarrow x\cdot w\in\Sigma^*$.

Here $\displaystyle \cdot$ is an infix notation for a binary function $\displaystyle \mbox{add}:\Sigma\times\Sigma^*\to\Sigma^*$ that adds a symbol $\displaystyle x$ to $\displaystyle w$ on the left, i.e., $\displaystyle x\cdot w=\mbox{add}(x,w)$. Thus, $\displaystyle \Sigma^*$ consists of terms $\displaystyle \mbox{add}(x_1,\mbox{add}(x_2,\dots,\mbox{add}(x_n ,\epsilon)\dots))$ where $\displaystyle x_1,\dots,x_n\in\Sigma$.

Let's define $\displaystyle f:\Sigma^*\to\Sigma^*$ by primitive recursion.

$\displaystyle f(\epsilon)=\epsilon$
$\displaystyle f(x\cdot w)=w$

Next, define $\displaystyle \mbox{rfl}:\Sigma^*\times\mathbb{N}\to\Sigma^*$.

$\displaystyle \mbox{rfl}(w,0)=w$
$\displaystyle \mbox{rfl}(w,S(n))=\dots$ (fill in the blank)

Disclaimer. The solution to this problem may depend a lot on the context of the course. First, strictly speaking, $\displaystyle \mbox{rfl}(w,0)=w$ is not a part of legal recursive schema. One should write $\displaystyle \mbox{rfl}(w,0)=P_1^2(w,0)$ where $\displaystyle P_i^n(x_1,\dots,x_n)=x_i$ is the projection function -- one of the base functions considered as given in primitive recursion. Usually such precision is not required.

Second, primitive recursive functions are traditionally defined for natural numbers. However, now, when programming languages like Haskell and ML allow defining new datatypes, it is clear that natural numbers is just the simplest nontrivial (i.e., infinite) example of an inductive type, where one constructor -- 0 -- is a constant and the other constructor -- S -- is a unary function. There is nothing special about this type. One may consider types with more than two constructors that are binary, ternary, etc. E.g., strings form an inductive type with one constant constructor -- $\displaystyle \epsilon$ -- and a binary constructor $\displaystyle \mbox{add}$. Correspondingly, the definition of primitive recursive functions is straightforwardly extended to these types.

Since you started by giving an inductive definition of $\displaystyle \Sigma^*\times\mathbb{N}$, I assumed that your instructor has this more liberal approach. Otherwise, you may consider recursion only on natural numbers and define functions on [tex]\Sigma^*[/MATH, say, using an English description. Then you can define f above using other means and consider only the equations for $\displaystyle \mbox{rfl}$.

If I did not address your question, feel free to give more details.