Diferencia entre revisiones de «Práctica 2 (LyC Verano)»

De Cuba-Wiki
 
(No se muestran 17 ediciones intermedias de 6 usuarios)
Línea 1: Línea 1:
__NOTOC__
{{Back|Lógica y Computabilidad}}
= Ejercicio 1 =
= 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>.
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>.
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 ==
=== Ítem a ===
 
<math>
<math>
\begin{cases}
\begin{cases}
f(x, 0) & = 17 \\
f(x, 0) & = 17 \\
f(x, y + 1) & = f(0, \phi(x, y)) \\
f(x, y + 1) & = f(0, \phi(x, y))
\end{cases}
\end{cases}
</math>
</math>


=== Solución ===
==== 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.
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>


== Ítem b ==
==== Solución ====
Definamos <math>f(x,y) = f'(x,y,y)\,\!</math>, Donde f' es


<math>
<math>
\begin{cases}
\begin{cases}
f(x, 0) & = \phi(x, x) \\
f'(x,y,0) & = \phi(x,x) \\
f(x, y + 1) &= f(\phi(x, y), y) \\
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
 
==== Otra Solución ====
Definamos
<math>
\mbox{f}(x, y) = \begin{cases}
\phi(x,x) & \mbox{si } y = 0 \\
\phi(K(x,y-1,y-1),K(x,y-1,y-1)) & \mbox{si } y > 0 \\
\end{cases}
\end{cases}
</math>
</math>


=== Solución ===
Donde K es


Definamos f(x,y) = f'(x,y,y), Donde f' es
<math>
<pre>
\begin{cases}
f'(x,y,0) = <math>\phi</math>(x,x)
K(x,y,0) & = \phi(x,y) \\
f'(x,y,i+1) = <math>\phi</math>(f'(x,y,i), y-i) = g(i, f'(x,y,i), x, y)
K(x,y,t+1) & = \phi(K(x,y,t), y-(t+1))
</pre>
\end{cases}
Entonces f' es PR -> f es PR
</math>


== Ítem c ==
Entonces f es PR por composición de funciones PR.


=== Ítem c ===
<math>
<math>
\begin{cases}
\begin{cases}
f(x, 0) & = \psi(x) \\
f(x, 0) & = \psi(x) \\
f(x, y + 1) & = f(x, y) + \phi(y, x)\\
f(x, y + 1) & = f(x, y) + \phi(y, x)
\end{cases}
\end{cases}
</math>
</math>


=== Solución ===
==== Solución ====
 
Se define:
Se define:


Línea 61: Línea 80:
Que es la forma buscada.
Que es la forma buscada.


 
=== Ítem d ===
== Ítem d ==
 
<math>
<math>
\begin{cases}
\begin{cases}
f(x, 0) & = \phi(0, x) \\
f(x, 0) & = \phi(0, x) \\
f(x, y + 1) & = \phi(f(x, y), y + 1)\\
f(x, y + 1) & = \phi(f(x, y), y + 1)
\end{cases}
\end{cases}
</math>
</math>


=== Solución ===
==== Solución ====
 
Se define:
Se define:


<math>g(a, b) = \phi(b, a + 1)\,\!</math>
<math>g(t,v,x) = \phi(v, t + 1)\,\!</math>


Que es p. r. por ser suma y composición. Luego,
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))\,\!</math>
<math>f(x, y + 1) = \phi(f(x, y), y + 1) = g(y, f(x, y),x)\,\!</math>


Que es la forma buscada.
Que es la forma buscada.


= Ejercicio 2 =
= Ejercicio 2 =
Línea 88: Línea 103:
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 97: Línea 111:
</math>
</math>


=== Solución ===
==== Solución ====


Definimos primero el decremento:
Definimos primero el decremento:
Línea 117: Línea 131:
</math>
</math>


== Ítem b ==
=== Ítem b ===
 
<math>
<math>
\mbox{min}(x, y) = \begin{cases}
\mbox{min}(x, y) = \begin{cases}
Línea 126: Línea 139:
</math>
</math>


=== Solución ===
==== Solución ====


Definimos la resta acotada:
Definimos la resta acotada:
Línea 141: Línea 154:
<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 151: Línea 163:
</math>
</math>


=== Solución ===
==== Solución ====


Definimos la negación:
Definimos la negación:
Línea 171: Línea 183:




== Í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 183: Línea 195:
\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 199: Línea 212:
<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 208: Línea 221:
</math>
</math>


=== Solución ===
==== Solución ====


Definimos igualdad,
Definimos igualdad,
Línea 222: Línea 235:
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 236: Línea 249:
</math>
</math>


=== Solución ===
==== Solución ====


Definimos exponenciación:
Definimos exponenciación:
Línea 260: Línea 273:
<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 273: Línea 286:
</math>
</math>


=== Solución ===
==== Solución ====


Definimos una función auxiliar:
Definimos una función auxiliar:
Línea 293: Línea 306:
</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 302: Línea 315:
f_2(x, 1) & = \phi(\phi(x, 1), 0) \\
f_2(x, 1) & = \phi(\phi(x, 1), 0) \\
& \vdots \\
& \vdots \\
f_2(x, y) & = \underbrace{\phi(\phi(\dots(\phi(\phi}_{y+1 \mbox{veces}}(x ,y), y 1 \dots), 1), 0) \\
f_2(x, y) & = \underbrace{\phi(\phi(\dots(\phi(\phi}_{y+1 \mbox{veces}}(x ,y), y - 1 \dots), 1), 0) \\
\end{cases}
\end{cases}
</math>
</math>


=== Solución ===
==== Solución ====


Definimos una función auxiliar:
Definimos una función auxiliar:
Línea 325: Línea 338:
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 341: Línea 354:
</math>
</math>


=== Solución ===
==== Solución ====


<math>f(x, y) = \begin{cases}
<math>f(x, y) = \begin{cases}
Línea 348: Línea 361:
\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 357: Línea 370:
</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 =
==== Otra Solución ====


Probar que las funciones <math>f_1\,\!</math> y <math>f_2\,\!</math> del [[Práctica_1_(Computabilidad)#Ejercicio_8 | ejercicio 8]] de la práctica de funciones computables son primitivas recursivas, siempre que g, s y t lo sean.
<math>f(w, x, y) = (x \le y) \cdot \prod_{i=x}^y (w \ge g(i)) \cdot (\sum_{j=x}^y (w = g(j)) \ge 1)  </math>


== Solución ==
= Ejercicio 5 =
 
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>
 
= Ejercicio 6 =


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 406: Línea 395:
</math>
</math>


== Ítem b ==
=== Ítem b ===


<math>\lg(x) = \begin{cases}
<math>\lg(x) = \begin{cases}
Línea 414: Línea 403:
</math>
</math>


=== Solución ===
==== Solución ====
 
<math>
<math>\lg(x) = \sum_{t=0}^x (2^t = x)</math>
\begin{cases}
\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 424: Línea 417:
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 7 =
= 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 8 =


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 464: Línea 456:
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 9 =
= 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 524: Línea 516:
</math>
</math>


= Ejercicio 10 =
==== Otra Solución ====
 
<math>\mbox{Sort}(x) = \mbox{min}_{t \le c(x)}
[(\forall 1 \le u \le |x|)(\mbox{Cant}(x[u], x) = \mbox{Cant}(x[u], t))] \cdot ((\sum_{j=1}^{|x|} \prod_{k=j}^{|x|} (t[j]) \le t[k])) = |x| )
</math>
 
= Ejercicio 9 =


Mostrar que la función de Fibonacci
Mostrar que la función de Fibonacci
Línea 538: Línea 536:
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) & = \ <0, 0> \\
\begin{cases}
f(1) & = \ <0, 1> \\
f(0) & = \ \langle 0, 0 \rangle \\
f(t + 1) & = \ <r(f(t)), r(f(t)) + l(f(t))> \\
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 11 =
= 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>


[[Category:Lógica y Computabilidad]]
= 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]]

Revisión actual - 02:24 23 sep 2013

Plantilla:Back

Ejercicio 1

Sean las funciones totales y . Sabiendo que la suma es una función recursiva, analizar si las siguientes definiciones de son definiciones por recursión primitiva a partir de y .

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 .

Ítem a

Solución

La función no es recursiva, alcanza con ver que si , nunca se puede descender al caso base.

Ítem b

Solución

Definamos , Donde f' es

Entonces f' es PR -> f es PR

Otra Solución

Definamos

Donde K es

Entonces f es PR por composición de funciones PR.

Ítem c

Solución

Se define:

Que es p. r. por ser suma y composición. Luego,

Que es la forma buscada.

Ítem d

Solución

Se define:

Que es p. r. por ser suma y composición. Luego,

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

Solución

Definimos primero el decremento:

Luego,

Ítem b

Solución

Definimos la resta acotada:

Luego,

Ítem c

Solución

Definimos la negación:

Luego,


Ítem d

Solución

Ítem e

Solución

Definimos producto:

Ítem f

Solución

Definimos igualdad,

Luego,

Ejercicio 3

Sean y funciones primitivas recursivas. Mostrar que las siguientes funciones también son primitivas recursivas.

Ítem a

La función definida como:

Solución

Definimos exponenciación:

Luego definimos una función auxiliar:

Entonces:

Ítem b

La función definida como:

Solución

Definimos una función auxiliar:

Ítem c

La función definida como:

Solución

Definimos una función auxiliar:

Luego,

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 es una función primitiva recursiva.

Ítem a

Solución

Ítem b

Solución

Ítem c

Solución

Otra Solución

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

Solución

Ítem b

Solución

Ítem c

el n-ésimo dígito en la representación binaria de , contando desde la derecha y comenzado con 0.

Así, , , , , , etc.

Solución

Ítem d

el número de unos en la representación binaria de .

Solución

Ítem e

es la cantidad de números primos entre y .

Solución


Ejercicio 6

Mostrar que la función es primitiva recursiva.

Solución

Ejercicio 7

Mostrar que la función definida como

cantidad de apariciones de en la lista

para todo es primitiva recursiva.

Solución

Ejercicio 8

Para , se define , donde la secuencia es una permutación de . Mostrar que 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 y el paso , observando la secuencia como un número de Gödel:

En el paso tenemos: , 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 queda: .

Además, sabemos que , y que (porque están fuera de orden), entonces:

Luego,

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:

Definimos una cota:

Y finalmente, buscamos la máxima permutación:

Otra Solución

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

para todo es primitiva recursiva.

Solución

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,