Funciones Primitivas Recursivas

Problema de Concatenación

$$\begin{array}{rl}\mathrm{concatenar}(w_1,w_2)& =\mathrm{Iconc}\circ (P_2^2\times P_1^2)(w_1,w_2)\\ \mathrm{Iconc}(w_2,w_1)& =\mathrm{concatenar}(w_2,w_1)\\ \mathrm{Iconc}(w_2,S_a(w_1))& =S_a\circ P_3^3(w_2,w_1,\mathrm{Iconc}(w_2,w_1))\\ \mathrm{Iconc}(w_2,S_b(w_1))& =S_b\circ P_3^3(w_2,w_1,\mathrm{Iconc}(w_2,w_1))\\ \mathrm{Iconc}(w_2,S_c(w_1))& =S_c\circ P_3^3(w_2,w_1,\mathrm{Iconc}(w_2,w_1))\end{array}$$

Operación de minimización

$$\begin{array}{r}f(x)=\text{micro}y[g(x,y)=0]\end{array}$$

Comprobar si la función $f(x)$ es computable es igual al menor valor de y que cumpla que la función $g(x,y)$ tiene un valor $0$, siempre que para todo valor menor que y la función $g(x,y)$ esté definida.

$$\begin{array}{rlrlrl}& g(0,0)=2& & g(1,0)=3& & g(2,0)=6\\ & g(0,1)=3& & g(1,1)=2& & g(2,1)=1\\ & g(0,2)=1& & g(1,2)=2& & g(2,2)->\text{no definido}\\ & g(0,3)=2& & \dots & & g(2,3)=3\\ & g(0,4)=4& & & & g(2,4)=0\\ & \dots & & & & \dots \\ & f(0)=4& & f(1)=2& & f(2)\text{no definida}\end{array}$$

Realizar

$$division(x,y)=conciente$$ $$\begin{array}{rl}& \text{Funciones baˊsicas y auxiliares (todas primitivas recursivas):}\\ & \text{Sucesor: }S(n)=n+1.\\ & \text{Suma y producto: }\mathrm{suma}(x,y),\mathrm{prod}(x,y)\text{por recursioˊn primitiva estaˊndar.}\\ & \text{Resta truncada: }\mathrm{rest}(x,y)=\max (x-y,0)\text{)}.\\ & \text{Prueba de cero: }is0(n)=\{\begin{array}{ll}1& \text{si }n=0,\\ 0& \text{si }n>0.\end{array}\\ & \text{Menor o igual: }\mathrm{leq}(x,y)=is0(\mathrm{rest}(x,y)).\\ & \text{Menor estricto: }\mathrm{lt}(x,y)=\mathrm{leq}(S(x),y).mprod(a,b)(a,b\in \{0,1\}).\\ & \text{Caracterizacioˊn del cociente entero:}\\ & q=\lfloor \frac{x}{y}\rfloor ⟺(y\cdot q\le x)\wedge (x<y\cdot (q+1)).\\ & \text{Traduccioˊn a PR sobre }\mathbb{N}:\\ & A(x,y,q)=\mathrm{rest}(\mathrm{prod}(y,q),x),\\ & B(x,y,q)=\mathrm{lt}(x,\mathrm{prod}(y,S(q)\left)\right),\\ & \text{entonces }\mathrm{ok}(x,y,q)=\mathrm{and}(is0(A(x,y,q)),B(x,y,q)),\\ & \text{y definimos }g(x,y,q)=1-\mathrm{ok}(x,y,q).\\ & \text{Definicioˊn }\mu \text{-recursiva de la divisioˊn entera (parcial):}\\ & \mathrm{division}(x,y)=\mu q[g(x,y,q)=0],\\ & \text{es decir, el menor }q\text{ tal que }\mathrm{prod}(y,q)\le x\text{ y }x<\mathrm{prod}(y,S(q)).\\ & \text{Dominio y parcialidad:}\\ & \text{Para }y>0,\exists q\le x\text{ uˊnico que satisface la condicioˊn, luego }\mathrm{division}(x,y)\text{ estaˊ definida.}\\ & \text{Para }y=0,\text{no existe tal }q\text{ y }\mathrm{division}(x,0)\text{ no estaˊ definida.}\end{array}$$

---

Problemas

$$\begin{array}{r}{f}_2:{\mathbb{N}}^2\to \mathbb{N}\\ (x,y)=x(x+1)\ast y\end{array}$$

Solución

$$\begin{array}{rl}& \text{Definicioˊn de }{f}_2:{\mathbb{N}}^2\to \mathbb{N}\\ & f_2(x,y)=x(x+1)y=\mathrm{prod}(\mathrm{prod}(x,S(x)),y).\\ & \text{Funciones auxiliares:}\\ & \text{Sucesor: }S(n)=n+1.\\ & \text{Producto:}\\ & \mathrm{prod}(x,0)=0,\\ & \mathrm{prod}(x,S(y))=\mathrm{suma}(\mathrm{prod}(x,y),x).\\ & \text{Suma:}\\ & \mathrm{suma}(x,0)=x,\\ & \mathrm{suma}(x,S(y))=S(\mathrm{suma}(x,y)).\end{array}$$

---

$$\begin{array}{r}\mathrm{AND}:{\mathbb{N}}^2\to \mathbb{N}\\ (x,y)=X\wedge Y\end{array}$$

Solución

$$\begin{array}{rl}& \\ & \text{Funciones baˊsicas y proyecciones:}\\ & P_i^n(x_1,\dots ,x_n)=x_i,0\text{(funcioˊn cero)},S(n)=n+1.\\ & \text{Suma (recursioˊn primitiva):}\\ & \mathrm{suma}(x,0)=P_1^1(x)=x,\\ & \mathrm{suma}(x,S(y))=S(\mathrm{suma}(x,y)).\\ & \text{Producto (recursioˊn primitiva):}\\ & \mathrm{prod}(x,0)=0,\\ & \mathrm{prod}(x,S(y))=\mathrm{suma}(\mathrm{prod}(x,y),x).\\ & \text{Conclusioˊn (con proyecciones):}\\ & \mathrm{AND}(x,y)=\mathrm{prod}(P_1^2(x,y),P_2^2(x,y)).\end{array}$$