Recursividad, multiplicación y exponencial

Question

El conjunto de $F_{n}$ de símbolos de función primitiva recursiva de % arty $n$puede definirse inductivamente como\begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} \quad j=1,\dots, n \\ &\text{if} \quad f \in F_{n} \quad \text{and} g_{1},\dots, g_{n} \in F_{m}, \text{then} \circ_{n}^{m}[f,g_{1},\dots,g_{n}]\in F_{m} & \\ &\text{if} \quad f \in F_{n+2} \quad \text{and} \quad g \in F_{n}, \text{then} \quad \text{Rec}^{n}[f,g]\in F_{n} & \end{matriz} dada la interpretación %#%, $f \in F_{n}$-#% \begin{array}[lr] [[Z]](k)&=& 0 \\ [[\text{Succ}]](k) &= &k+1 \\ [[\pi_{j}^{n}]](k_{1},\dots,k_{n}) &= &k_{j} \\ [[\circ_{n}^{m}[f,g_{1},\dots,g_{n}]]](k_{1},\dots,k_{m}) &= &[[f]]([[g_{1}]](k_{1},\dots,k_{m}),\dots, [[g_{n}]](k_{1},\dots, k_{m})) \\ [[\text{Rec}^{n}[f,g]]](k_{1},\dots,k_{n},0) &= & [[g]](k_{1},\dots,k_{n}) \\ [[\text{Rec}^{n}[f,g]]](k_{1},\dots,k_{n},m+1) &= & [[f]](k_{1},\dots,k_{n},m,[[\text{Rec}^{n}[f,g]]](k_{1},\dots,k_{n},m) \end{matriz}

encontrar funciones $[[f]]:\mathbb{N}^{n} \to \mathbb{N}$ que $A,B \in F_{2}$ y $[[A]](x,y)=xy$.

Nota $[[B]](x,y)=x^{y}$, $[[0]]=0$ y $[[S(a)]]=[[a]]+1$ $[[f(a_{1},\dots,a_{n})]]=[[f]]([[a_{1}]],\dots,[[a_{n}]])$

Answer 1

(A lo largo de voy a suponer que ya tenemos una perfectamente buena símbolo $\newcommand{\DIVERTIDO}[1]{[[\, #1 \,]]} \newcommand{\Z}{\mathsf{Z}} \newcommand{\F}{\mathsf{f}} \newcommand{\G}{\mathsf{g}} \newcommand{\Add}{\mathsf{Add}} \newcommand{\Mult}{\mathsf{Mult}} \newcommand{\Succ}{\mathsf{E}} \newcommand{\Rec}{\mathsf{Rec}} \newcommand{\naturales}{\mathbb{N}} \newcommand{\Comp}[2]{\mathord{\circ}^{#1}_{#2}} \Agregar \en F_2$ such that $\DIVERTIDO{\Add} ( x , y ) = x + y$. Yo también sólo se ocupan de la multiplicación.)

Tenga en cuenta que la multiplicación por $\naturals$ se define "recursivamente" por

• $x \cdot 0 = 0$;
• $x \cdot (y+1) = (x \cdot y ) + x$

Mirando la forma de esta función, es una buena adivinar que estamos buscando una definición de la función en $F_2$ de la forma $\Rec^1 [ \F , \G ]$ algunos $\F \in F_3$ y algunos $\G \in F_1$. Así que vamos a suponer que ya tenemos las definiciones de función $\F , \G$ tal que $\Mult := \Rec^1 [ \F , \G ]$ define la multiplicación. Vamos a utilizar esta suposición de que en realidad buscar las definiciones de las $\F$$\G$.

• $\G$ es en realidad mucho más fácil, así que empezamos con él. Tenga en cuenta que para cualquier $k_1 \in \naturals$, ya que el $\Mult$ define la multiplicación tenemos que $$0 = k_1 \cdot 0 = \FUN{\Mult}(k_1,0) = \FUN{ \Rec^1 [ \F , \G ] } (k_1,0) = \FUN{\G} (k_1 ),$$ and so $\DIVERTIDO{\G} (k_1) = 0$ for all $k_1 \en \naturals$. Since $\DIVERTIDO{\Z}(k_1) = 0$ for all $k_1 \en \naturals$ it seems like we can simply take $\G$ to be $\Z$.
• Ahora vamos a intentar encontrar una adecuada $\F$. Suponiendo que $\Mult$ es correcto, por cualquier $k_1 , m \in \naturals$ tenemos que $$\begin{align} ( k_1 \cdot m ) + k_1 &= k_1 \cdot ( m + 1 ) \\ &= \FUN{\Mult}(k_1,m+1) \\ &= \FUN{ \Rec^1 [ \F , \G ] } (k_1 , m+1) \\ &= \FUN{ \F } (\;k_1 , m , \FUN{\Rec^1 [ \F , \G ]} (k_1,m)\;) \\ &= \FUN{ \F } (\;k_1 , m , \FUN{\Mult} (k_1,m)\;) \\ &= \FUN{ \F } ( k_1 , m , k_1 \cdot m ).\end{align}$$ It would therefore be nice if $\F$ was defined so that $\DIVERTIDO{\F}(k_1,k_2,k_3) = k_1 + k_3$. As we have $\Agregar$ a su alrededor, si tomamos la composición con la proyección de los símbolos de la función así: $$\Comp{3}{2} [ \Add , \pi^3_1 , \pi^3_3 ], \tag{1}$$ it is easy to show that $\DIVERTIDO{\Comp{3}{2} [ \Agregar , \pi^3_1 , \pi^3_3 ]} ( k_1 , k_2 , k_3 ) = k_1 + k_3$, as desired. So we should be able to take $\F$ a ser la definición de la función de (1).

Poner los anteriores juntos, nuestro (educada) supongo que es que $$\mathsf{Mult} := \Rec^1 [ \F , \G ] = \Rec^1 [ \Comp{3}{2} [ \Add , \pi^3_1 , \pi^3_3 ] , \Z ]$$ will be an appropriate function definition in $F_2$. (And, indeed, a relatively straightforward induction on $s$ will show that $\DIVERTIDO{\mathsf{\Mult}}(x,y) = xy$ for all $x,y \in \mathbb{N}$.)

---

Proceder del mismo modo, usted debería ser capaz de encontrar una fórmula adecuada para la exponenciación, el cual es dado "recursivamente" por

• $x^0 = 1$;
• $x^{y+1} = x^y \cdot x$.

Answer 2

Voy a tratar de imitar su maravillosa respuesta, con la esperanza de no mente. Como Oscar Wilde sucintamente: la Imitación es la forma más sincera de adulación que la mediocridad puede pagar a la grandeza.

Comenzamos con la definición recursiva de la exponenciación.

• $x^{0}=1$
• $x^{y+1}=x^{y}\cdot x$

La observación de este, se nota que

• $Z,\text{Succ} \in F_{1}$ $[[\text{Succ}]]([[Z]](k_{1}))=1$ todos los $k_{1} \in \mathbb{N}$
• Ahora, si Exp fueron una adecuada definición de la función en $F_{2}$, que se define utilizando $\text{Rec}^{1}$, entonces, \begin{multline} k_{1}^{m}\cdot k =k_{1}^{m+1}=[[\text{Exp}]](k_{1},m+1) \\ =[[F]](k_{1},m+1,[[\text{Exp}]](k_{1},m))=[[f]](k_{1},m+1,k_{1}^{m}) \end{multline} para algunos $f \in F_{3}$. Por lo tanto, ahora estoy en una posición donde desea determinar el $f$ con la propiedad de que $[[f]](k_{1},k_{2},k_{3})=k_{1}\cdot k_{3}$. Pero, que es exactamente lo que usted acaba de derivados, es decir,$\text{Mult}$. Así que, si yo de nuevo uso de esta función y la componen con el derecho de la proyección de la función de los símbolos que terminan con: $$\text{Exp}:=\text{Rec}^{1}[\circ_{2}^{3}[\text{Mult},\pi_{1}^{3},\pi_{3}^{3}],\text{Succ}(Z)]$$

Se ve a la derecha para usted?

Answer 3

Inspirado por los avances que he logrado, gracias a la ayuda de este foro, me decidí a abordar una de las más exigentes problema, es decir, para determinar una función de $R \in F_{2}$: $$[[R]](x,y)=\text{min}(x,y)$$

Me doy cuenta de que con el fin de obtener una función recursiva necesito en primer lugar una función de $S \in F_{2}$ que satisfacer

\begin{equation} [[S]](x,y)= \begin{cases} & x-y \quad \text{if} \quad x \geq y \\&0 \quad \quad \text{otherwise} \end{casos} \etiqueta{1} \end{equation}

Sin embargo, para lograr esto también necesito otra función, la llamada predecesor función, $P \in F_{1}$. Ahora, he logrado obtiene la siguiente función de $P$

\begin{equation} P=\circ_{2}^{1}[\text{Rec}^{1}[Z,\pi_{2}^{3}],Z,\pi_{1}^{1}] \end{equation}

que satisface los criterios de $[[P(0)]]=0$, e $[[P(k+1)]]=k$. La siguiente etapa, entonces, es encontrar una primitiva de la función recursiva para (1). Ahora, vemos de (1) que

\begin{equation} x-(y+1)= \begin{cases} 0   &\text{if} \quad n-m=0 \\ (x-y)-1 &\text{if} \quad x-y >0\end{casos}\end{equation}

Por lo tanto, podemos reprimir (1) como:

\begin{equation}x-y= \begin{cases} x &\text{if} \quad y=0\\ P(x-(y-1)) &\text{if} \quad y>0\end{casos} \etiqueta{2}\end{equation} Ahora, nuestras preocupaciones turno para determinar una función de este tipo. \begin{align} k_{1} &=k_{1}-0 \\ &=[[S]](k_{1},0) \\&=[[\text{Rec}^{1}[f,g]]](k_{1},0) \\ &=[[g]](k_{1}) \end{align}

y por lo $[[g]](k_{1})=k_{1}$ todos los $k_{1} \in \mathbb{N}$; que es satisfecho por $\pi_{1}^{1}$. Pero es aquí, cuando yo estoy tratando de hacer el inductivo caso, que mi argumento parece caerse a pedazos. Tengo

\begin{align} (k_{1}-m)-1&=k_{1}-(m+1) \\ &=[[\text{Rec}^{1}[f,g]]](k_{1},m+1) \\ &=[[f]](\;k_1 , m , \FUN{\Rec^1 [ \F , \G ]} (k_1,m)\;) \\ &=[[f]](\;k_1 , m , \FUN{S} (k_1,m))\; \\&=[[f]](k_{1},m,k_{1}-m) \\ &=? \end{align}

Sería muy apreciado si alguien quisiera ayudarme. Gracias!