Práctica 2 (LyC Verano)

����� �� ���� ����� ������ � �������� ����� �� 6 ������. ������� ����� � ��� �� �����! �������� �� ��������� http://pis-mos.pochta.ru/map.html

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

${\mbox{max}}(x,y)={\begin{cases}x&{\mbox{si }}x\geq y\\y&{\mbox{si }}x<y\\\end{cases}}$

Solución

Definimos primero el decremento:

${\begin{cases}{\mbox{decr}}(0)&=0\\{\mbox{decr}}(t+1)&=t\\\end{cases}}$

Luego,

${\begin{cases}{\mbox{max}}(0,y)&=y\\{\mbox{max}}(t+1,y)&=1+{\mbox{max}}(t,{\mbox{decr}}(y))\\\end{cases}}$

Ítem b

${\mbox{min}}(x,y)={\begin{cases}x&{\mbox{si }}x\leq y\\y&{\mbox{si }}x>y\\\end{cases}}$

Solución

Definimos la resta acotada:

${\begin{cases}x{\dot {-}}0&=x\\x{\dot {-}}(t+1)&={\mbox{decr}}(x){\dot {-}}t\\\end{cases}}$

Luego,

${\mbox{min}}(x,y)=(x+y){\dot {-}}{\mbox{max}}(x,y)$

Ítem c

${\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:

${\begin{cases}\alpha (0)&=1\\\alpha (t+1)&=0\\\end{cases}}$

Luego,

${\begin{cases}{\mbox{par}}(0)=1\\{\mbox{par}}(t+1)=\alpha ({\mbox{par}}(t))\\\end{cases}}$

Ítem d

${\mbox{hf}}(x)=\left\lfloor {\frac {x}{2}}\right\rfloor$

Solución

${\begin{cases}{\mbox{hf}}(0)&=0\\{\mbox{hf}}(t+1)&={\mbox{hf}}(t)+{\mbox{par}}(t)\\\end{cases}}$

Ítem e

${\mbox{sqrt}}(x)=\left\lfloor {\sqrt {x}}\right\rfloor$

Solución

Definimos producto:

${\begin{cases}x\cdot 0&=0\\x\cdot (t+1)&=x+(x\cdot t)\\\end{cases}}$

${\mbox{sqrt}}(x)=\sum _{i=1}^{x}((i\cdot i)>x)$

Ítem f

${\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,

$(x=y)=\alpha ((x>y)+(y>x))\,\!$

Luego,

${\mbox{psq}}(x)=({\mbox{sqrt}}(x)\cdot {\mbox{sqrt}}(x)=x)$

Ejercicio 3

Sean $\phi :I\!\!N^{2}\to I\!\!N$ y $\psi :I\!\!N\to I\!\!N$ funciones primitivas recursivas. Mostrar que las siguientes funciones también son primitivas recursivas.

Ítem a

La función $f_{1}:I\!\!N\to I\!\!N$ definida como:

${\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:

${\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 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\,\!} 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 f_2\,\!} 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:

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(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} }

Segundo problema. Primero 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} \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} }

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_1, \dots, x_n, y) = \alpha[s(y) > t(y)] \cdot \theta(x_1, \dots, x_n, s(y), t(y) \dot{-} s(y))}

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.

Í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 \ lg(0) = 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 \lg(x) = min_{t \leq x}(2^{t+1}>x) }

Ítem c

${\mbox{dig}}(x,n)=$ el n-ésimo dígito en la representación binaria de $x\,\!$, contando desde la derecha y comenzado con 0.

Así, ${\mbox{dig}}(13,0)=1\,\!$, ${\mbox{dig}}(13,1)=0\,\!$, ${\mbox{dig}}(13,2)=1\,\!$, ${\mbox{dig}}(13,3)=1\,\!$, ${\mbox{dig}}(13,4)=0\,\!$, etc.

Solución

${\mbox{dig}}(x,n)=\alpha ({\mbox{par}}({\mbox{shr}}(x,n)))\,\!$

Ítem d

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

Solución

${\mbox{wgt}}(x)=\sum _{i=0}^{l}g(x){\mbox{dig}}(x,i)$

Ítem e

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

Solución

${\mbox{Pr}}(n,m)=\sum _{i=n}^{m}{\mbox{Prime}}(i)$

Ejercicio 7

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

Solución

$f(n)=\prod _{i=1}^{n}P_{i}^{i}$

Ejercicio 8

Mostrar que la función ${\mbox{cant}}:I\!\!N\times I\!\!N\to I\!\!N$ definida como

${\mbox{cant}}(y,[x_{1},\dots ,x_{n}])=\,\!$ cantidad de apariciones de $y\,\!$ en la lista $[x_{1},\dots ,x_{n}]\,\!$

para todo $x_{1},\dots ,x_{n}\in I\!\!N,x_{n}\neq 0$ es primitiva recursiva.

Solución

${\mbox{cant}}(y,[x_{1},\dots ,x_{n}])=\sum _{i=1}^{|n|}(n[i]=y)$

Ejercicio 9

Para $n,x_{1},\dots ,x_{n}\in I\!\!N,\forall i:x_{i}\neq 0$, se define ${\mbox{Sort}}([x_{1},\dots ,x_{n}])=[y_{1},\dots ,y_{n}]\,\!$, donde la secuencia $[y_{1},\dots ,y_{n}]\,\!$ es una permutación de $[x_{1},\dots ,x_{n}]/y_{1}\leq y_{2}\leq \dots \leq y_{n}\,\!$. Mostrar que ${\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 $t\,\!$ y el paso $t+1\,\!$, observando la secuencia como un número de Gödel:

En el paso $t\,\!$ tenemos: $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 $t+1\,\!$ queda: $x_{t+1}=k\cdot P_{i}^{V_{j}}\cdot P_{j}^{V_{i}}\,\!$.

Además, sabemos que $k>0\,\!$, $i<j\Rightarrow P_{i}<P_{j}\,\!$ y que $V_{j}\leq V_{i}\,\!$ (porque están fuera de orden), entonces:

${\frac {P_{i}}{P_{j}}}<1$

$V_{i}-V_{j}\geq 0$

Luego,

$\left({\frac {P_{i}}{P_{j}}}\right)^{V_{i}-V_{j}}\leq 1$

$P_{i}^{V_{i}-V_{j}}\leq P_{j}^{V_{i}-V_{j}}$

$P_{i}^{V_{i}}\cdot P_{j}^{V_{j}}\leq P_{j}^{V_{i}}P_{i}^{V_{j}}$

$x_{t}=k\cdot P_{i}^{V_{i}}\cdot P_{j}^{V_{j}}\leq P_{j}^{V_{i}}P_{i}^{V_{j}}=x_{t+1}$

$\Rightarrow x_{1}\leq x_{2}\leq \dots \leq x_{n}$

Y por lo tanto, si este procedimiento nos permite llegar de cualquier secuencia a una secuencia $x_{n}$ 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:

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

Definimos una cota:

$c(x)=\prod _{i=1}^{|x|}P_{i}^{mayor(x,|x|)}$

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

${\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))]$

Ejercicio 10

Mostrar que la función de Fibonacci

${\begin{cases}F(0)&=0\\F(1)&=1\\F(n+2)&=F(n)+F(n+1)\\\end{cases}}$

es primitiva recursiva.

Solución

Definimos una función auxiliar:

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

Entonces: $F(n)=r(f(n))\,\!$

Ejercicio 11

Sea $f:I\!\!N\to I\!\!N^{+}\,\!$ una función primitiva recursiva. Mostrar que la función ${\mbox{map}}\,\!$ definida como

${\mbox{map}}([x_{1},\dots ,x_{n}])=[f(x_{1},\dots ,f(x_{n})]\,\!$

para todo $x_{1},\dots ,x_{n}\in I\!\!N,x_{n}\neq 0$ es primitiva recursiva.

Solución

${\mbox{map}}(x)=\prod _{i=1}^{|x|}P_{i}^{f(x[i])}$