Edición de «Práctica 2 (LyC Verano)»

__NOTOC__
{{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

==== 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}
</math>

Donde K es

<math>
\begin{cases}
K(x,y,0) & = \phi(x,y) \\
K(x,y,t+1) & = \phi(K(x,y,t), y-(t+1))
\end{cases}
</math>

Entonces f es PR por composición de funciones 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 =

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 ===
<math>
\mbox{max}(x, y) = \begin{cases}
x & \mbox{si } x \ge y \\
y & \mbox{si } x < y \\
\end{cases}
</math>

==== Solución ====

Definimos primero el decremento:

<math>
\begin{cases}
\mbox{decr}(0) & = 0 \\
\mbox{decr}(t + 1) & = t \\
\end{cases}
</math>

Luego, 

<math>
\begin{cases}
\mbox{max}(0, y) & = y \\
\mbox{max}(t + 1, y) & = 1 + \mbox{max}(t, \mbox{decr}(y)) \\
\end{cases}
</math>

=== Ítem b ===
<math>
\mbox{min}(x, y) = \begin{cases}
x & \mbox{si } x \le y \\
y & \mbox{si } x > y \\
\end{cases}
</math>

==== Solución ====

Definimos la resta acotada:

<math>
\begin{cases}
x \dot - 0 & = x \\
x \dot - (t + 1) & = \mbox{decr}(x) \dot - t \\
\end{cases}
</math>

Luego,

<math>\mbox{min}(x, y) = (x + y) \dot - \mbox{max}(x, y)</math>

=== Ítem c ===

<math>
\mbox{par}(x) = \begin{cases}
1 & \mbox{si } x \mbox{ es par} \\
0 & \mbox{si } x \mbox{ es impar} \\
\end{cases}
</math>

==== Solución ====

Definimos la negación:

<math>\begin{cases}
\alpha(0) & = 1 \\
\alpha(t + 1) & = 0 \\
\end{cases}
</math>

Luego,

<math>
\begin{cases}
\mbox{par}(0) = 1 \\
\mbox{par}(t + 1) = \alpha(\mbox{par}(t)) \\
\end{cases}
</math>


=== Ítem d ===

<math>\mbox{hf}(x) = \left \lfloor \frac{x}{2} \right \rfloor</math>

==== Solución ====

<math>
\begin{cases}
\mbox{hf}(0) & = 0 \\
\mbox{hf}(t + 1) & = \mbox{hf}(t) + \mbox{par}(t) \\
\end{cases}
</math>

=== Ítem e ===

<math>\mbox{sqrt}(x) = \left \lfloor \sqrt{x} \right \rfloor</math>

==== Solución ====

Definimos producto:

<math>\begin{cases}
x \cdot 0 & = 0 \\
x \cdot (t + 1) & = x + (x \cdot t) \\
\end{cases}
</math>

<math>\mbox{sqrt}(x) = \sum_{i=1}^x ((i \cdot i) > x)</math>

=== Ítem f ===

<math>
\mbox{psq}(x) = \begin{cases}
1 & \mbox{si } x \mbox{ es un cuadrado perfecto} \\
0 & \mbox{si } \mbox{en otro caso} \\
\end{cases}
</math>

==== Solución ====

Definimos igualdad,

<math>(x = y) = \alpha((x > y) + (y > x))\,\!</math>

Luego,

<math>\mbox{psq}(x) = (\mbox{sqrt}(x) \cdot \mbox{sqrt}(x) = x)</math>

= Ejercicio 3 =

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 ===

La función <math>f_1: I\!\!N \to I\!\!N</math> definida como:

<math>
\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}
</math>

==== Solución ====

Definimos exponenciación:

<math>
\begin{cases}
x^0 & = 1 \\
x^{t + 1} & = x \cdot x^t \\
\end{cases}
</math>

Luego definimos una función auxiliar:

<math>
\begin{cases}
\mbox{supexp}(a, b, 0) & = a \\
\mbox{supexp}(a, b, t + 1) & = \mbox{supexp}(a, b, t)^b \\
\end{cases}
</math>

Entonces:

<math>f_1(n) = \mbox{superexp}(n, n, n)\,\!</math>

=== Ítem b ===

La función <math>f_2: I\!\!N \to I\!\!N</math> definida como:

<math>
\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}
</math>

==== Solución ====

Definimos una función auxiliar:

<math>\lambda(x, n) = \underbrace{\psi(\psi(\dots(\psi}_{n+1 \mbox{veces}}(x) + 1) \dots) + 1)</math>

<math>
\begin{cases}
\lambda(x, 0) & = \psi(x) \\
\lambda(x, t + 1) & = \psi(\lambda(x, t) + 1) \\
\end{cases}
</math>

<math>
f_2(x) = \begin{cases}
\psi(x) & \mbox{si } x = 0 \\
\lambda(x, x) + 1 & \mbox{sino} \\
\end{cases}
</math>

=== Ítem c ===

La función <math>f_3: I\!\!N^2 \to I\!\!N</math> definida como:

<math>
\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}
</math>

==== Solución ====

Definimos una función auxiliar:

<math>
\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}
</math>

Luego,

<math>f_2(x) = \sigma(x, y, y)</math>

= 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 <math>g: I\!\!N \to I\!\!N</math> es una función primitiva recursiva.

=== Ítem a ===

<math>f(x, y) = \sharp\{i : 0 \le i \le x \land g(i) > y\}</math>

==== Solución ====

<math>f(x, y) = \sum_{i=0}^x (g(i) > y)</math>

=== Ítem b ===

<math>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}
</math>

==== Solución ====

<math>f(x, y) = \begin{cases}
0 & \mbox{si } x > y \\
\prod_{i=x}^y (g(i + 1) > g(i)) & \mbox{sino}
\end{cases}</math>

=== Ítem c ===

<math>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}
</math>

==== 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>

= 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 ===

<math>\mbox{shr}(x, n) = \left \lfloor \frac{x}{2^n} \right \rfloor</math>

==== Solución ====

<math>
\begin{cases}
\mbox{shr}(x, 0) & =  x \\
\mbox{shr}(x, t + 1) & =  \mbox{hf}(\mbox{shr}(x, t)) \\
\end{cases}
</math>

=== Ítem b ===

<math>\lg(x) = \begin{cases}
0 & \mbox{si } x = 0 \\
\left \lfloor \log_2(x) + 1 \right \rfloor & \mbox{en otro caso} \\
\end{cases}
</math>

==== Solución ====
<math>
\begin{cases}
\lg(0) & = 0 \\
\lg(x) & = min_{t \leq x}(2^{t+1}>x)
\end{cases}
</math>

=== Í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.

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 ====

<math>\mbox{dig}(x, n) = \alpha(\mbox{par}(\mbox{shr}(x, n)))\,\!</math>

=== Ítem d ===

<math>\mbox{wgt}(x) = </math> el número de unos en la representación binaria de 
<math>x\,\!</math>.

==== Solución ====

<math>\mbox{wgt}(x) = \sum_{i=0}^{lg(x)} \mbox{dig}(x, i)</math>

=== Ítem e ===

<math>\mbox{Pr}(n, m) = </math> es la cantidad de números primos entre
<math>n\,\!</math> y <math>m\,\!</math>.

==== Solución ====

<math>\mbox{Pr}(n, m) = \sum_{i=n}^m \mbox{Prime}(i)</math>


= Ejercicio 6 =

Mostrar que la función <math>f: I\!\!N \to I\!\!N / f(n) = [1, \dots, n]</math>  es primitiva recursiva.

==== Solución ====

<math>f(n) = \prod_{i=1}^n P_i^i</math>

= Ejercicio 7 =

Mostrar que la función <math>\mbox{cant}: I\!\!N \times I\!\!N \to I\!\!N</math>  definida como

<center><math>\mbox{cant}(y, [x_1, \dots, x_n]) =\,\!</math> cantidad de apariciones de <math>y\,\!</math> en la lista <math>[x_1, \dots, x_n]\,\!</math></center>

para todo <math>x_1, \dots, x_n \in I\!\!N, x_n \ne 0</math> es primitiva recursiva.

==== Solución ====

<math>\mbox{cant}(y, [x_1, \dots, x_n]) = \sum_{i=1}^{|n|}(n[i] = y)</math>

= 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.

==== 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 <math>t\,\!</math> y el paso <math>t + 1\,\!</math>, observando la secuencia como un número de Gödel:

En el paso <math>t\,\!</math> tenemos: <math>x_t = k \cdot P_i^{V_i} \cdot  P_j^{V_j}\,\!</math>, 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 <math>t + 1\,\!</math> queda: <math>x_{t+1} = k \cdot P_i^{V_j} \cdot  P_j^{V_i}\,\!</math>.

Además, sabemos que <math>k > 0\,\!</math>, <math>i < j \Rightarrow P_i < P_j\,\!</math> y que <math>V_j \le V_i\,\!</math> (porque están fuera de orden), entonces:

<center><math>\frac{P_i}{P_j} < 1</math>

<math>V_i - V_j \ge 0</math>
</center>

Luego, 

<center>
<math>\left ( \frac{P_i}{P_j} \right ) ^{V_i - V_j} \le 1</math>

<math>P_i^{V_i - V_j} \le P_j^{V_i - V_j}</math>

<math>P_i^{V_i} \cdot P_j^{V_j} \le P_j^{V_i} P_i^{V_j}</math>

<math>x_t = k \cdot P_i^{V_i} \cdot P_j^{V_j} \le P_j^{V_i} P_i^{V_j} = x_{t+1}</math>

<math>\Rightarrow x_1 \le x_2 \le \dots \le x_n</math>
</center>

Y por lo tanto, si este procedimiento nos permite llegar de cualquier secuencia a una secuencia <math>x_n</math> 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:

<math>
\begin{cases}
\mbox{mayor}(x, 1) & = x[1] \\
\mbox{mayor}(x, t + 1) & = \mbox{max}(\mbox{mayor}(x, t), x[t + 1]) \\
\end{cases}
</math>

Definimos una cota:

<math>c(x) = \prod_{i=1}^{|x|} P_i^{mayor(x, |x|)}</math>

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

<math>\mbox{Sort}(x) = \mbox{max}_{t \le c(x)}
[(\forall 1 \le u \le |x|)(\mbox{Cant}(x[u], x) = \mbox{Cant}(x[u], t))]
</math>

==== 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

<math>
\begin{cases}
F(0) & = 0 \\
F(1) & = 1 \\
F(n + 2) & = F(n) + F(n + 1) \\
\end{cases}
</math>

es primitiva recursiva.

==== Solución ====

Definimos una función auxiliar:

<math>
\begin{cases}
f(0) & = \ \langle 0, 0 \rangle \\
f(1) & = \ \langle 0, 1 \rangle \\
f(t + 1) & = \ \langle r(f(t)), r(f(t)) + l(f(t)) \rangle \\
\end{cases}
</math>

Entonces:
<math>F(n) = r(f(n))\,\!</math>

= 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

<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.

==== Solución ====

<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]]