Diferencia entre revisiones de «Práctica 2 (LyC Verano)»
| (No se muestran 4 ediciones intermedias del mismo usuario) | |||
| Línea 1: | Línea 1: | ||
__NOTOC__ | |||
{{Back|Lógica y Computabilidad}} | {{Back|Lógica y Computabilidad}} | ||
= Ejercicio 1 = | |||
Sean las funciones totales <math>\phi: I\!\!N^2 \to I\!\!N</math> y <math>\psi: I\!\!N \to I\!\!N</math>. Sabiendo que la suma es una función recursiva, analizar si las siguientes definiciones de <math>f\,\!</math> son definiciones por recursión primitiva a partir de <math>\phi\,\!</math> y <math>\psi\,\!</math>. | |||
Para cada una de las definiciones que representen una recursión primitiva, especificar las funciones asociadas al esquema de recursión primitiva a partir del cual se obtiene <math>f\,\!</math>. | |||
=== Ítem a === | |||
<math> | |||
\begin{cases} | |||
f(x, 0) & = 17 \\ | |||
f(x, y + 1) & = f(0, \phi(x, y)) | |||
\end{cases} | |||
</math> | |||
==== Solución ==== | |||
La función no es recursiva, alcanza con ver que si <math>\phi(x, y) \ge y)\,\!</math>, nunca se puede descender al caso base. | |||
=== Ítem b === | |||
<math> | |||
\begin{cases} | |||
f(x, 0) & = \phi(x, x) \\ | |||
f(x, y + 1) & = f(\phi(x, y), y) | |||
\end{cases} | |||
</math> | |||
==== Solución ==== | |||
Definamos <math>f(x,y) = f'(x,y,y)\,\!</math>, Donde f' es | |||
<math> | |||
\begin{cases} | |||
f'(x,y,0) & = \phi(x,x) \\ | |||
f'(x,y,i+1) & = \phi(f'(x,y,i), y-i) = g(i, f'(x,y,i), x, y) | |||
\end{cases} | |||
</math> | |||
Entonces f' es PR -> f es PR | |||
=== Ítem c === | |||
<math> | |||
\begin{cases} | |||
f(x, 0) & = \psi(x) \\ | |||
f(x, y + 1) & = f(x, y) + \phi(y, x) | |||
\end{cases} | |||
</math> | |||
==== Solución ==== | |||
Se define: | |||
<math>g(a, b, c) = b + \phi(a,c)\,\!</math> | |||
Que es p. r. por ser suma y composición. Luego, | |||
<math> | |||
f(x, y + 1) = f(x, y) + \phi(y, x) | |||
= g(y, f(x, y), x)\,\! | |||
</math> | |||
Que es la forma buscada. | |||
=== Ítem d === | |||
<math> | |||
\begin{cases} | |||
f(x, 0) & = \phi(0, x) \\ | |||
f(x, y + 1) & = \phi(f(x, y), y + 1) | |||
\end{cases} | |||
</math> | |||
==== Solución ==== | |||
Se define: | |||
<math>g(t,v,x) = \phi(v, t + 1)\,\!</math> | |||
Que es p. r. por ser suma y composición. Luego, | |||
<math>f(x, y + 1) = \phi(f(x, y), y + 1) = g(y, f(x, y),x)\,\!</math> | |||
Que es la forma buscada. | |||
= Ejercicio 2 = | = Ejercicio 2 = | ||
| Línea 8: | Línea 83: | ||
Probar que las siguientes funciones son primitivas recursivas, mostrando que pueden obtenerse a partir de las funciones iniciales o a través de composición o recursión primitiva. | Probar que las siguientes funciones son primitivas recursivas, mostrando que pueden obtenerse a partir de las funciones iniciales o a través de composición o recursión primitiva. | ||
== Ítem a == | === Ítem a === | ||
<math> | <math> | ||
\mbox{max}(x, y) = \begin{cases} | \mbox{max}(x, y) = \begin{cases} | ||
| Línea 17: | Línea 91: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
Definimos primero el decremento: | Definimos primero el decremento: | ||
| Línea 37: | Línea 111: | ||
</math> | </math> | ||
== Ítem b == | === Ítem b === | ||
<math> | <math> | ||
\mbox{min}(x, y) = \begin{cases} | \mbox{min}(x, y) = \begin{cases} | ||
| Línea 46: | Línea 119: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
Definimos la resta acotada: | Definimos la resta acotada: | ||
| Línea 61: | Línea 134: | ||
<math>\mbox{min}(x, y) = (x + y) \dot - \mbox{max}(x, y)</math> | <math>\mbox{min}(x, y) = (x + y) \dot - \mbox{max}(x, y)</math> | ||
=== Ítem c === | |||
== Ítem c == | |||
<math> | <math> | ||
| Línea 71: | Línea 143: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
Definimos la negación: | Definimos la negación: | ||
| Línea 91: | Línea 163: | ||
== Ítem d == | === Ítem d === | ||
<math>\mbox{hf}(x) = \left \lfloor \frac{x}{2} \right \rfloor</math> | <math>\mbox{hf}(x) = \left \lfloor \frac{x}{2} \right \rfloor</math> | ||
=== Solución === | ==== Solución ==== | ||
<math> | <math> | ||
| Línea 103: | Línea 175: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
== Ítem e == | |||
=== Ítem e === | |||
<math>\mbox{sqrt}(x) = \left \lfloor \sqrt{x} \right \rfloor</math> | <math>\mbox{sqrt}(x) = \left \lfloor \sqrt{x} \right \rfloor</math> | ||
=== Solución === | ==== Solución ==== | ||
Definimos producto: | Definimos producto: | ||
| Línea 119: | Línea 192: | ||
<math>\mbox{sqrt}(x) = \sum_{i=1}^x ((i \cdot i) > x)</math> | <math>\mbox{sqrt}(x) = \sum_{i=1}^x ((i \cdot i) > x)</math> | ||
== Ítem f == | === Ítem f === | ||
<math> | <math> | ||
| Línea 128: | Línea 201: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
Definimos igualdad, | Definimos igualdad, | ||
| Línea 142: | Línea 215: | ||
Sean <math>\phi: I\!\!N^2 \to I\!\!N</math> y <math>\psi: I\!\!N \to I\!\!N</math> funciones primitivas recursivas. Mostrar que las siguientes funciones también son primitivas recursivas. | Sean <math>\phi: I\!\!N^2 \to I\!\!N</math> y <math>\psi: I\!\!N \to I\!\!N</math> funciones primitivas recursivas. Mostrar que las siguientes funciones también son primitivas recursivas. | ||
== Ítem a == | === Ítem a === | ||
La función <math>f_1: I\!\!N \to I\!\!N</math> definida como: | La función <math>f_1: I\!\!N \to I\!\!N</math> definida como: | ||
| Línea 156: | Línea 229: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
Definimos exponenciación: | Definimos exponenciación: | ||
| Línea 180: | Línea 253: | ||
<math>f_1(n) = \mbox{superexp}(n, n, n)\,\!</math> | <math>f_1(n) = \mbox{superexp}(n, n, n)\,\!</math> | ||
== Ítem b == | === Ítem b === | ||
La función <math>f_2: I\!\!N \to I\!\!N</math> definida como: | La función <math>f_2: I\!\!N \to I\!\!N</math> definida como: | ||
| Línea 193: | Línea 266: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
Definimos una función auxiliar: | Definimos una función auxiliar: | ||
| Línea 213: | Línea 286: | ||
</math> | </math> | ||
== Ítem c == | === Ítem c === | ||
La función <math>f_3: I\!\!N^2 \to I\!\!N</math> definida como: | La función <math>f_3: I\!\!N^2 \to I\!\!N</math> definida como: | ||
| Línea 226: | Línea 299: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
Definimos una función auxiliar: | Definimos una función auxiliar: | ||
| Línea 245: | Línea 318: | ||
Usar las definiciones por sumas y/o productos acotados para establecer la recursividad primitiva de cada una de las siguientes funciones. Suponer que <math>g: I\!\!N \to I\!\!N</math> es una función primitiva recursiva. | Usar las definiciones por sumas y/o productos acotados para establecer la recursividad primitiva de cada una de las siguientes funciones. Suponer que <math>g: I\!\!N \to I\!\!N</math> es una función primitiva recursiva. | ||
== Ítem a == | === Ítem a === | ||
<math>f(x, y) = \sharp\{i : 0 \le i \le x \land g(i) > y\}</math> | <math>f(x, y) = \sharp\{i : 0 \le i \le x \land g(i) > y\}</math> | ||
=== Solución === | ==== Solución ==== | ||
<math>f(x, y) = \sum_{i=0}^x (g(i) > y)</math> | <math>f(x, y) = \sum_{i=0}^x (g(i) > y)</math> | ||
== Ítem b == | === Ítem b === | ||
<math>f(x, y) = \begin{cases} | <math>f(x, y) = \begin{cases} | ||
| Línea 261: | Línea 334: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
<math>f(x, y) = \begin{cases} | <math>f(x, y) = \begin{cases} | ||
| Línea 268: | Línea 341: | ||
\end{cases}</math> | \end{cases}</math> | ||
== Ítem c == | === Ítem c === | ||
<math>f(w, x, y) = \begin{cases} | <math>f(w, x, y) = \begin{cases} | ||
| Línea 277: | Línea 350: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
<math>f(w, x, y) = \alpha(x > y) \cdot \prod_{i=x}^y \alpha(w < g(i)) \cdot \alpha(\alpha(\sum_{i=x}^y (w = g(i)))</math> | <math>f(w, x, y) = \alpha(x > y) \cdot \prod_{i=x}^y \alpha(w < g(i)) \cdot \alpha(\alpha(\sum_{i=x}^y (w = g(i)))</math> | ||
= Ejercicio 5 = | = Ejercicio 5 = | ||
Probar que las funciones dadas a continuación son primitivas recursivas. Pueden usarse como funciones auxiliares las dadas en las clases teóricas y prácticas o las ya calculadas anteriormente. | Probar que las funciones dadas a continuación son primitivas recursivas. Pueden usarse como funciones auxiliares las dadas en las clases teóricas y prácticas o las ya calculadas anteriormente. | ||
== Ítem a == | === Ítem a === | ||
<math>\mbox{shr}(x, n) = \left \lfloor \frac{x}{2^n} \right \rfloor</math> | <math>\mbox{shr}(x, n) = \left \lfloor \frac{x}{2^n} \right \rfloor</math> | ||
=== Solución === | ==== Solución ==== | ||
<math> | <math> | ||
| Línea 326: | Línea 371: | ||
</math> | </math> | ||
== Ítem b == | === Ítem b === | ||
<math>\lg(x) = \begin{cases} | <math>\lg(x) = \begin{cases} | ||
| Línea 334: | Línea 379: | ||
</math> | </math> | ||
=== Solución === | ==== Solución ==== | ||
<math> | |||
\begin{cases} | |||
<math>\ lg(0) = 0 | \lg(0) & = 0 \\ | ||
\lg(x) & = min_{t \leq x}(2^{t+1}>x) | |||
\end{cases} | |||
</math> | |||
== Ítem c == | === Ítem c === | ||
<math>\mbox{dig}(x, n) = </math> el n-ésimo dígito en la representación binaria de <math>x\,\!</math>, contando desde la derecha y comenzado con 0. | <math>\mbox{dig}(x, n) = </math> el n-ésimo dígito en la representación binaria de <math>x\,\!</math>, contando desde la derecha y comenzado con 0. | ||
| Línea 347: | Línea 393: | ||
Así, <math>\mbox{dig}(13, 0) = 1\,\!</math>, <math>\mbox{dig}(13, 1) = 0\,\!</math>, <math>\mbox{dig}(13, 2) = 1\,\!</math>, <math>\mbox{dig}(13, 3) = 1\,\!</math>, <math>\mbox{dig}(13, 4) = 0\,\!</math>, etc. | Así, <math>\mbox{dig}(13, 0) = 1\,\!</math>, <math>\mbox{dig}(13, 1) = 0\,\!</math>, <math>\mbox{dig}(13, 2) = 1\,\!</math>, <math>\mbox{dig}(13, 3) = 1\,\!</math>, <math>\mbox{dig}(13, 4) = 0\,\!</math>, etc. | ||
=== Solución === | ==== Solución ==== | ||
<math>\mbox{dig}(x, n) = \alpha(\mbox{par}(\mbox{shr}(x, n)))\,\!</math> | <math>\mbox{dig}(x, n) = \alpha(\mbox{par}(\mbox{shr}(x, n)))\,\!</math> | ||
== Ítem d == | === Ítem d === | ||
<math>\mbox{wgt}(x) = </math> el número de unos en la representación binaria de | <math>\mbox{wgt}(x) = </math> el número de unos en la representación binaria de | ||
<math>x\,\!</math>. | <math>x\,\!</math>. | ||
=== Solución === | ==== Solución ==== | ||
<math>\mbox{wgt}(x) = \sum_{i=0}^lg(x) \mbox{dig}(x, i)</math> | <math>\mbox{wgt}(x) = \sum_{i=0}^lg(x) \mbox{dig}(x, i)</math> | ||
== Ítem e == | === Ítem e === | ||
<math>\mbox{Pr}(n, m) = </math> es la cantidad de números primos entre | <math>\mbox{Pr}(n, m) = </math> es la cantidad de números primos entre | ||
<math>n\,\!</math> y <math>m\,\!</math>. | <math>n\,\!</math> y <math>m\,\!</math>. | ||
=== Solución === | ==== Solución ==== | ||
<math>\mbox{Pr}(n, m) = \sum_{i=n}^m \mbox{Prime}(i)</math> | <math>\mbox{Pr}(n, m) = \sum_{i=n}^m \mbox{Prime}(i)</math> | ||
= Ejercicio | = Ejercicio 6 = | ||
Mostrar que la función <math>f: I\!\!N \to I\!\!N / f(n) = [1, \dots, n]</math> es primitiva recursiva. | Mostrar que la función <math>f: I\!\!N \to I\!\!N / f(n) = [1, \dots, n]</math> es primitiva recursiva. | ||
=== Solución === | ==== Solución ==== | ||
<math>f(n) = \prod_{i=1}^n P_i^i</math> | <math>f(n) = \prod_{i=1}^n P_i^i</math> | ||
= Ejercicio 7 = | |||
= Ejercicio | |||
Mostrar que la función <math>\mbox{cant}: I\!\!N \times I\!\!N \to I\!\!N</math> definida como | Mostrar que la función <math>\mbox{cant}: I\!\!N \times I\!\!N \to I\!\!N</math> definida como | ||
| Línea 387: | Línea 432: | ||
para todo <math>x_1, \dots, x_n \in I\!\!N, x_n \ne 0</math> es primitiva recursiva. | para todo <math>x_1, \dots, x_n \in I\!\!N, x_n \ne 0</math> es primitiva recursiva. | ||
=== Solución === | ==== Solución ==== | ||
<math>\mbox{cant}(y, [x_1, \dots, x_n]) = \sum_{i=1}^{|n|}(n[i] = y)</math> | <math>\mbox{cant}(y, [x_1, \dots, x_n]) = \sum_{i=1}^{|n|}(n[i] = y)</math> | ||
= Ejercicio | = Ejercicio 8 = | ||
Para <math>n, x_1, \dots, x_n \in I\!\!N, \forall i : x_i \ne 0</math>, se define <math>\mbox{Sort}([x_1, \dots, x_n]) = [y_1, \dots, y_n]\,\!</math>, donde la secuencia <math>[y_1, \dots, y_n]\,\!</math> es una permutación de <math>[x_1, \dots, x_n] / y_1 \le y_2 \le \dots \le y_n\,\!</math>. Mostrar que <math>\mbox{Sort}\,\!</math> es primitiva recursiva. | Para <math>n, x_1, \dots, x_n \in I\!\!N, \forall i : x_i \ne 0</math>, se define <math>\mbox{Sort}([x_1, \dots, x_n]) = [y_1, \dots, y_n]\,\!</math>, donde la secuencia <math>[y_1, \dots, y_n]\,\!</math> es una permutación de <math>[x_1, \dots, x_n] / y_1 \le y_2 \le \dots \le y_n\,\!</math>. Mostrar que <math>\mbox{Sort}\,\!</math> es primitiva recursiva. | ||
=== Solución === | ==== Solución ==== | ||
Sabemos que podemos obtener una secuencia ordenada con una serie de permutaciones de a dos elementos que están fuera de orden el uno con respecto al otro, como lo hace Bubble Sort. (Habría que probar esto?) | Sabemos que podemos obtener una secuencia ordenada con una serie de permutaciones de a dos elementos que están fuera de orden el uno con respecto al otro, como lo hace Bubble Sort. (Habría que probar esto?) | ||
| Línea 447: | Línea 492: | ||
</math> | </math> | ||
= Ejercicio | = Ejercicio 9 = | ||
Mostrar que la función de Fibonacci | Mostrar que la función de Fibonacci | ||
| Línea 461: | Línea 506: | ||
es primitiva recursiva. | es primitiva recursiva. | ||
=== Solución === | ==== Solución ==== | ||
Definimos una función auxiliar: | Definimos una función auxiliar: | ||
<math>\begin{cases} | <math> | ||
f(0) & = \ | \begin{cases} | ||
f(1) & = \ | f(0) & = \ \langle 0, 0 \rangle \\ | ||
f(t + 1) & = \ | f(1) & = \ \langle 0, 1 \rangle \\ | ||
\end{cases}</math> | f(t + 1) & = \ \langle r(f(t)), r(f(t)) + l(f(t)) \rangle \\ | ||
\end{cases} | |||
</math> | |||
Entonces: | Entonces: | ||
<math>F(n) = r(f(n))\,\!</math> | <math>F(n) = r(f(n))\,\!</math> | ||
= Ejercicio | = Ejercicio 10 = | ||
Sea <math>f: I\!\!N \to I\!\!N^+\,\!</math> una función primitiva recursiva. Mostrar que la función <math>\mbox{map}\,\!</math> definida como | Sea <math>f: I\!\!N \to I\!\!N^+\,\!</math> una función primitiva recursiva. Mostrar que la función <math>\mbox{map}\,\!</math> definida como | ||
<center><math>\mbox{map}([x_1, \dots, x_n]) = [f(x_1, \dots, f(x_n)]\,\!</math></center> | <center><math>\mbox{map}([x_1, \dots, x_n]) = [f(x_1), \dots, f(x_n)]\,\!</math></center> | ||
para todo <math>x_1, \dots, x_n \in I\!\!N, x_n \ne 0</math> es primitiva recursiva. | para todo <math>x_1, \dots, x_n \in I\!\!N, x_n \ne 0</math> es primitiva recursiva. | ||
=== Solución === | ==== Solución ==== | ||
<math>\mbox{map}(x) = \prod_{i=1}^{|x|}P_i^{f(x[i])}</math> | <math>\mbox{map}(x) = \prod_{i=1}^{|x|}P_i^{f(x[i])}</math> | ||
= Ejercicio Extra 1 = | |||
Probar que las funciones <math>f_1\,\!</math> y <math>f_2\,\!</math> del Ejercicio 8 de la práctica de funciones computables son primitivas recursivas, siempre que g, s y t lo sean. | |||
== Solución == | |||
Primer problema: | |||
<math> | |||
\begin{cases} | |||
f_1(x_1, \dots, x_n, 0) & = g(x_1, \dots, x_n, 0) \\ | |||
f_1(x_1, \dots, x_n, t + 1) & = \mbox{max}(f_1(x_1, \dots, x_n, t), g(x_1, \dots, x_n, t + 1) \\ | |||
\end{cases} | |||
</math> | |||
Segundo problema. Primero definimos una función auxiliar: | |||
<math> | |||
\begin{cases} | |||
\theta(x_1, \dots, x_n, z, 0) & = g(x_1, \dots, x_n, z) \\ | |||
\theta(x_1, \dots, x_n, z, t + 1) & = \mbox{max}(\theta(x_1, \dots, x_n, z, t), g(x_1, \dots, x_n, z + t + 1) \\ | |||
\end{cases} | |||
</math> | |||
Luego, | |||
<math>f_2(x_1, \dots, x_n, y) = \alpha[s(y) > t(y)] \cdot \theta(x_1, \dots, x_n, s(y), t(y) \dot{-} s(y))</math> | |||
[[Category:Prácticas]] | [[Category:Prácticas]] | ||
Revisión del 14:25 1 feb 2009
Ejercicio 1
Sean las funciones totales Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi: I\!\!N^2 \to I\!\!N} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \psi: I\!\!N \to I\!\!N} . Sabiendo que la suma es una función recursiva, analizar si las siguientes definiciones de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f\,\!} son definiciones por recursión primitiva a partir de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi\,\!} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \psi\,\!} .
Para cada una de las definiciones que representen una recursión primitiva, especificar las funciones asociadas al esquema de recursión primitiva a partir del cual se obtiene Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f\,\!} .
Ítem a
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} f(x, 0) & = 17 \\ f(x, y + 1) & = f(0, \phi(x, y)) \end{cases} }
Solución
La función no es recursiva, alcanza con ver que si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi(x, y) \ge y)\,\!} , nunca se puede descender al caso base.
Ítem b
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} f(x, 0) & = \phi(x, x) \\ f(x, y + 1) & = f(\phi(x, y), y) \end{cases} }
Solución
Definamos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x,y) = f'(x,y,y)\,\!} , Donde f' es
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} f'(x,y,0) & = \phi(x,x) \\ f'(x,y,i+1) & = \phi(f'(x,y,i), y-i) = g(i, f'(x,y,i), x, y) \end{cases} }
Entonces f' es PR -> f es PR
Ítem c
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} f(x, 0) & = \psi(x) \\ f(x, y + 1) & = f(x, y) + \phi(y, x) \end{cases} }
Solución
Se define:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(a, b, c) = b + \phi(a,c)\,\!}
Que es p. r. por ser suma y composición. Luego,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x, y + 1) = f(x, y) + \phi(y, x) = g(y, f(x, y), x)\,\! }
Que es la forma buscada.
Ítem d
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} f(x, 0) & = \phi(0, x) \\ f(x, y + 1) & = \phi(f(x, y), y + 1) \end{cases} }
Solución
Se define:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g(t,v,x) = \phi(v, t + 1)\,\!}
Que es p. r. por ser suma y composición. Luego,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x, y + 1) = \phi(f(x, y), y + 1) = g(y, f(x, y),x)\,\!}
Que es la forma buscada.
Ejercicio 2
Probar que las siguientes funciones son primitivas recursivas, mostrando que pueden obtenerse a partir de las funciones iniciales o a través de composición o recursión primitiva.
Ítem a
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{max}(x, y) = \begin{cases} x & \mbox{si } x \ge y \\ y & \mbox{si } x < y \\ \end{cases} }
Solución
Definimos primero el decremento:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \mbox{decr}(0) & = 0 \\ \mbox{decr}(t + 1) & = t \\ \end{cases} }
Luego,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \mbox{max}(0, y) & = y \\ \mbox{max}(t + 1, y) & = 1 + \mbox{max}(t, \mbox{decr}(y)) \\ \end{cases} }
Ítem b
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{min}(x, y) = \begin{cases} x & \mbox{si } x \le y \\ y & \mbox{si } x > y \\ \end{cases} }
Solución
Definimos la resta acotada:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} x \dot - 0 & = x \\ x \dot - (t + 1) & = \mbox{decr}(x) \dot - t \\ \end{cases} }
Luego,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{min}(x, y) = (x + y) \dot - \mbox{max}(x, y)}
Ítem c
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{par}(x) = \begin{cases} 1 & \mbox{si } x \mbox{ es par} \\ 0 & \mbox{si } x \mbox{ es impar} \\ \end{cases} }
Solución
Definimos la negación:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \alpha(0) & = 1 \\ \alpha(t + 1) & = 0 \\ \end{cases} }
Luego,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \mbox{par}(0) = 1 \\ \mbox{par}(t + 1) = \alpha(\mbox{par}(t)) \\ \end{cases} }
Ítem d
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{hf}(x) = \left \lfloor \frac{x}{2} \right \rfloor}
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \mbox{hf}(0) & = 0 \\ \mbox{hf}(t + 1) & = \mbox{hf}(t) + \mbox{par}(t) \\ \end{cases} }
Ítem e
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{sqrt}(x) = \left \lfloor \sqrt{x} \right \rfloor}
Solución
Definimos producto:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} x \cdot 0 & = 0 \\ x \cdot (t + 1) & = x + (x \cdot t) \\ \end{cases} }
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{sqrt}(x) = \sum_{i=1}^x ((i \cdot i) > x)}
Ítem f
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{psq}(x) = \begin{cases} 1 & \mbox{si } x \mbox{ es un cuadrado perfecto} \\ 0 & \mbox{si } \mbox{en otro caso} \\ \end{cases} }
Solución
Definimos igualdad,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (x = y) = \alpha((x > y) + (y > x))\,\!}
Luego,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{psq}(x) = (\mbox{sqrt}(x) \cdot \mbox{sqrt}(x) = x)}
Ejercicio 3
Sean Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi: I\!\!N^2 \to I\!\!N} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \psi: I\!\!N \to I\!\!N} funciones primitivas recursivas. Mostrar que las siguientes funciones también son primitivas recursivas.
Ítem a
La función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_1: I\!\!N \to I\!\!N} definida como:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} f_1(0) & = 0 \\ f_1(1) & = 1 \\ f_1(2) & = 2^2 \\ & \vdots \\ f_1(n) & = \underbrace{n^{n^{\cdot^{\cdot^{\cdot^{n}}}}}}_{n \mbox{veces}} \\ \end{cases} }
Solución
Definimos exponenciación:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} x^0 & = 1 \\ x^{t + 1} & = x \cdot x^t \\ \end{cases} }
Luego definimos una función auxiliar:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \mbox{supexp}(a, b, 0) & = a \\ \mbox{supexp}(a, b, t + 1) & = \mbox{supexp}(a, b, t)^b \\ \end{cases} }
Entonces:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_1(n) = \mbox{superexp}(n, n, n)\,\!}
Ítem b
La función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_2: I\!\!N \to I\!\!N} definida como:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} f_2(0) & = \psi(0) \\ f_2(1) & = \psi(\psi(1) + 1) + 1 \\ & \vdots \\ f_2(x) & = \underbrace{\psi(\psi(\dots(\psi}_{x+1 \mbox{veces}}(x) + 1) \dots) + 1) + 1 \\ \end{cases} }
Solución
Definimos una función auxiliar:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda(x, n) = \underbrace{\psi(\psi(\dots(\psi}_{n+1 \mbox{veces}}(x) + 1) \dots) + 1)}
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \lambda(x, 0) & = \psi(x) \\ \lambda(x, t + 1) & = \psi(\lambda(x, t) + 1) \\ \end{cases} }
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_2(x) = \begin{cases} \psi(x) & \mbox{si } x = 0 \\ \lambda(x, x) + 1 & \mbox{sino} \\ \end{cases} }
Ítem c
La función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_3: I\!\!N^2 \to I\!\!N} definida como:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} f_2(x, 0) & = \phi(x, 0) \\ f_2(x, 1) & = \phi(\phi(x, 1), 0) \\ & \vdots \\ f_2(x, y) & = \underbrace{\phi(\phi(\dots(\phi(\phi}_{y+1 \mbox{veces}}(x ,y), y 1 \dots), 1), 0) \\ \end{cases} }
Solución
Definimos una función auxiliar:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \sigma(x, y, 0) & = \phi(x, y) \\ \sigma(x, y, t + 1) & = \phi(\sigma(x, y, t), y \dot - (t + 1)) \\ \end{cases} }
Luego,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_2(x) = \sigma(x, y, y)}
Ejercicio 4
Usar las definiciones por sumas y/o productos acotados para establecer la recursividad primitiva de cada una de las siguientes funciones. Suponer que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g: I\!\!N \to I\!\!N} es una función primitiva recursiva.
Ítem a
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x, y) = \sharp\{i : 0 \le i \le x \land g(i) > y\}}
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x, y) = \sum_{i=0}^x (g(i) > y)}
Ítem b
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x, y) = \begin{cases} 1 & \mbox{si } g(i + 1) > g(i) \mbox{ para todos los valores de } t / x \le i \le y \\ 0 & \mbox{en otro caso} \end{cases} }
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(x, y) = \begin{cases} 0 & \mbox{si } x > y \\ \prod_{i=x}^y (g(i + 1) > g(i)) & \mbox{sino} \end{cases}}
Ítem c
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(w, x, y) = \begin{cases} 1 & \mbox{si } x \le y \mbox{ y } w \mbox{ es el mayor entre } g(x), g(x+1), \dots, g(y) \\ 0 & \mbox{en otro caso} \end{cases} }
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(w, x, y) = \alpha(x > y) \cdot \prod_{i=x}^y \alpha(w < g(i)) \cdot \alpha(\alpha(\sum_{i=x}^y (w = g(i)))}
Ejercicio 5
Probar que las funciones dadas a continuación son primitivas recursivas. Pueden usarse como funciones auxiliares las dadas en las clases teóricas y prácticas o las ya calculadas anteriormente.
Ítem a
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{shr}(x, n) = \left \lfloor \frac{x}{2^n} \right \rfloor}
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \mbox{shr}(x, 0) & = x \\ \mbox{shr}(x, t + 1) & = \mbox{hf}(\mbox{shr}(x, t)) \\ \end{cases} }
Ítem b
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lg(x) = \begin{cases} 0 & \mbox{si } x = 0 \\ \left \lfloor \log_2(x) + 1 \right \rfloor & \mbox{en otro caso} \\ \end{cases} }
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \begin{cases} \lg(0) & = 0 \\ \lg(x) & = min_{t \leq x}(2^{t+1}>x) \end{cases} }
Ítem c
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{dig}(x, n) = } el n-ésimo dígito en la representación binaria de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x\,\!} , contando desde la derecha y comenzado con 0.
Así, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{dig}(13, 0) = 1\,\!} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{dig}(13, 1) = 0\,\!} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{dig}(13, 2) = 1\,\!} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{dig}(13, 3) = 1\,\!} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{dig}(13, 4) = 0\,\!} , etc.
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{dig}(x, n) = \alpha(\mbox{par}(\mbox{shr}(x, n)))\,\!}
Ítem d
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{wgt}(x) = } el número de unos en la representación binaria de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x\,\!} .
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{wgt}(x) = \sum_{i=0}^lg(x) \mbox{dig}(x, i)}
Ítem e
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{Pr}(n, m) = } es la cantidad de números primos entre Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n\,\!} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle m\,\!} .
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{Pr}(n, m) = \sum_{i=n}^m \mbox{Prime}(i)}
Ejercicio 6
Mostrar que la función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f: I\!\!N \to I\!\!N / f(n) = [1, \dots, n]} es primitiva recursiva.
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f(n) = \prod_{i=1}^n P_i^i}
Ejercicio 7
Mostrar que la función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{cant}: I\!\!N \times I\!\!N \to I\!\!N} definida como
para todo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_1, \dots, x_n \in I\!\!N, x_n \ne 0} es primitiva recursiva.
Solución
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{cant}(y, [x_1, \dots, x_n]) = \sum_{i=1}^{|n|}(n[i] = y)}
Ejercicio 8
Para Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n, x_1, \dots, x_n \in I\!\!N, \forall i : x_i \ne 0} , se define Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{Sort}([x_1, \dots, x_n]) = [y_1, \dots, y_n]\,\!} , donde la secuencia Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle [y_1, \dots, y_n]\,\!} es una permutación de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle [x_1, \dots, x_n] / y_1 \le y_2 \le \dots \le y_n\,\!} . Mostrar que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mbox{Sort}\,\!} es primitiva recursiva.
Solución
Sabemos que podemos obtener una secuencia ordenada con una serie de permutaciones de a dos elementos que están fuera de orden el uno con respecto al otro, como lo hace Bubble Sort. (Habría que probar esto?)
Entonces, comparamos el paso Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle t\,\!} y el paso Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle t + 1\,\!} , observando la secuencia como un número de Gödel:
En el paso Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle t\,\!} tenemos: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_t = k \cdot P_i^{V_i} \cdot P_j^{V_j}\,\!} , donde se observan los dos elementos que se van a permutar y la constante que representa al resto de la secuencia que no se modifica.
En el paso Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle t + 1\,\!} queda: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_{t+1} = k \cdot P_i^{V_j} \cdot P_j^{V_i}\,\!} .
Además, sabemos que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k > 0\,\!} , Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle i < j \Rightarrow P_i < P_j\,\!} y que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_j \le V_i\,\!} (porque están fuera de orden), entonces:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_i - V_j \ge 0}
Luego,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \left ( \frac{P_i}{P_j} \right ) ^{V_i - V_j} \le 1}
Y por lo tanto, si este procedimiento nos permite llegar de cualquier secuencia a una secuencia ordenada, tenemos que el número de Gödel de la secuencia ordenada es el mayor de los números de todas las permutaciones.
Entonces, definimos una función que busca el mayor elemento de la secuencia:
![{\displaystyle {\begin{cases}{\mbox{mayor}}(x,1)&=x[1]\\{\mbox{mayor}}(x,t+1)&={\mbox{max}}({\mbox{mayor}}(x,t),x[t+1])\\\end{cases}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/4662180b87301d22c124ee1f9b77ccd445e32f0f)
Definimos una cota:
Y finalmente, buscamos la máxima permutación:
![{\displaystyle {\mbox{Sort}}(x)={\mbox{max}}_{t\leq c(x)}[(\forall 1\leq u\leq |x|)({\mbox{Cant}}(x[u],x)={\mbox{Cant}}(x[u],t))]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/21f9d97fa68f1ea2b09401f1476e862a278f2d55)
Ejercicio 9
Mostrar que la función de Fibonacci
es primitiva recursiva.
Solución
Definimos una función auxiliar:
Entonces:
Ejercicio 10
Sea una función primitiva recursiva. Mostrar que la función definida como
![{\displaystyle {\mbox{map}}([x_{1},\dots ,x_{n}])=[f(x_{1}),\dots ,f(x_{n})]\,\!}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/cc0daa8574ddd67cbc266d2ba35e976a5f24eb9f)
para todo es primitiva recursiva.
Solución
![{\displaystyle {\mbox{map}}(x)=\prod _{i=1}^{|x|}P_{i}^{f(x[i])}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/1fdcdda27f072cbb1245ac46bfbe32c3b4df98d8)
Ejercicio Extra 1
Probar que las funciones y del Ejercicio 8 de la práctica de funciones computables son primitivas recursivas, siempre que g, s y t lo sean.
Solución
Primer problema:
Segundo problema. Primero definimos una función auxiliar:
Luego,
![{\displaystyle f_{2}(x_{1},\dots ,x_{n},y)=\alpha [s(y)>t(y)]\cdot \theta (x_{1},\dots ,x_{n},s(y),t(y){\dot {-}}s(y))}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/1ec1f2d4a9400200c9c08876ac0b32355000b511)
