Práctica 1 (LyC Verano)

Ejercicio 1

Sin usar macros, mostrar en ${\mathcal {S}}$ un programa que compute la función vacía $\emptyset :I\!\!N^{k}\to I\!\!N$; es decir, la función que no está definida para ninguna k-tupla de naturales.

Solución

     Y ← Y + 1
[A1] IF Y ≠ 0 GOTO A1

Ejercicio 2

Escribir en ${\mathcal {S}}$ programas que computen los siguientes predicados.

Pueden utilizarse las macros

GOTO A

(salto incondicional),

V ← k

(asignación de constantes) y

V1 ← V2

(asignación de variables).

Ítem a

$igual(x_{1},x_{2})={\begin{cases}1&{\mbox{si }}x_{1}=x_{2}\\0&{\mbox{si }}x_{1}\neq x_{2}\\\end{cases}}$

Solución

[A1] IF X1 ≠ 0 GOTO A2
     IF X2 ≠ 0 GOTO E
     Y ← Y + 1
     GOTO E
[A2] IF X2 ≠ 0 GOTO A3
     GOTO E
[A3] X1 ← X1 - 1
     X2 ← X2 - 1
     GOTO A1

Ítem b

$distinto(x_{1},x_{2})={\begin{cases}1&{\mbox{si }}x_{1}\neq x_{2}\\0&{\mbox{si }}x_{1}=x_{2}\\\end{cases}}$

Solución

     Y ← Y + 1
[A1] IF X1 ≠ 0 GOTO A2
     IF X2 ≠ 0 GOTO E
     Y ← Y - 1
     GOTO E
[A2] IF X1 ≠ 0 GOTO A3
     GOTO E
[A3] X1 ← X1 - 1
     X2 ← X2 - 1
     GOTO A1

Ítem c

$mayor(x_{1},x_{2})={\begin{cases}1&{\mbox{si }}x_{1}>x_{2}\\0&{\mbox{si }}x_{1}\leq x_{2}\\\end{cases}}$

Solución

[A1] IF X1 ≠ 0 GOTO A2
     GOTO E
[A2] IF X2 ≠ 0 GOTO A3
     Y ← Y + 1
     GOTO E
[A3] X1 ← X1 - 1
     X2 ← X2 - 1
     GOTO A1

Ítem d

$menor(x_{1},x_{2})={\begin{cases}1&{\mbox{si }}x_{1}<x_{2}\\0&{\mbox{si }}x_{1}\geq x_{2}\\\end{cases}}$

Solución

[A1] IF X2 ≠ 0 GOTO A2
     GOTO E
[A2] IF X1 ≠ 0 GOTO A3
     Y ← Y + 1
     GOTO E
[A3] X1 ← X1 - 1
     X2 ← X2 - 1
     GOTO A1

Ejercicio 3

Escribir en ${\mathcal {S}}$ programas que calculen las siguientes funciones.

Además, pueden utilizarse las macros

GOTO A

,

V ← k

y

V1 ← V2

.

Ítem a

$producto(x_{1},x_{2})=x_{1}\cdot x_{2}$ (usando suma como macro)

Solución

     Z1 ← X1
[A1] IF Z1 ≠ 0 GOTO A2
     GOTO E
[A2] Y ← Y + X2
     Z1 ← Z1 - 1
     GOTO A1

Ítem b

$potencia(x_{1},x_{2})=x_{1}^{x_{2}}$ (usando producto como macro)

Solución

     Z1 ← X2
     Y ← 1
[A1] IF Z1 ≠ 0 GOTO A2
     GOTO E
[A2] Y ← Y * X1
     Z1 ← Z1 - 1
     GOTO A1

Ejercicio 4

Demostrar que las siguientes funciones son computables:

• la función sucesor $suc:I\!\!N\to I\!\!N,suc(x)=x+1$
• las proyecciones $u_{i}^{n}:I\!\!N^{n}\to I\!\!N,u_{i}^{n}(x_{1},\dots ,x_{n})=x_{i}$ (para $i$ tal que $i\leq i\leq n)$.
• las funciones constantes $c_{k}:I\!\!N\to I\!\!N,c_{k}(x)=k$ (para cualquier $k\in I\!\!N$).

Solución

$suc(x)\,\!$

     Y ← X1 + 1

$u_{i}^{n}(x_{1},\dots ,x_{n})\,\!$

     Y ← Xi

$c_{k}(x)\,\!$

     Y ← k

Ejercicio 5

Usando las macros vistas en clase, escribir programas en ${\mathcal {S}}$ que computen las siguientes funciones:

Ítem a

$f(x)=\,\!$ el mayor número natural $n\,\!$ tal que $2n\leq x\,\!$

Solución

[A1] Z1 ← Z1 + 2
     Z2 ← Z1 > X1
     IF Z2 ≠ 0 GOTO E
     Y ← Y + 1
     GOTO A1

Ítem b

$P(x_{1},x_{2})={\begin{cases}1&{\mbox{si }}x_{2}{\mbox{ es multiplo de }}x_{1}\\0&{\mbox{sino}}\\\end{cases}}\,\!$

Solución

     IF Z2 = 0 GOTO A2 // si Z2 = 0 entonces es múltiplo de X1 
                       // voy a A2 y como Z1 = X2 = 0  devuelvo 1  
[A1] Z1 ← Z1 + X1      // Z1 guarda los múltiplos de X1
     Z2 ← Z1 < X2
     IF Z2 ≠ 0 GOTO A1
[A2] Y ← Y + 1          // se tiene Z1 = k * X1 >= X2 
     Z3 ← Z1 = X2
     IF Z3 ≠ 0 GOTO E
     Y ← Y - 1

Ejercicio 6

Escribir un programa que compute el mínimo común múltiplo y otro que compute el máximo común divisor entre dos números naturales. Se puede utilizar cualquier macro vista en clase.

Solución

$MCM:\ \mathbb {N} \times \mathbb {N} \rightarrow \mathbb {N}$

     Y ← X1
[A]  Z ← multiplo(Y, X2)
     IF Z ≠ 0 GOTO E
     Y ← Y + X1   // Y = X1, 2X1, 3X1....
     GOTO A

$MCD:\ \mathbb {N} \times \mathbb {N} \rightarrow \mathbb {N}$

    Y ← X1
    Z2 ← X2
[A] IF Z2 = 0 GOTO E
[B]    Z3 ← mayor(Y,Z2)
       IF Z3 ≠ 0 GOTO C
          Z2 ← Z2 - Y
          GOTO A
[C]       Y ← Y - Z2
          GOTO A

IDEA: ALGORITMO DE EUCLIDES ORIGINAL

 MCD(a,b) = 
  while (b > 0) {
    if (a > b)
       then a <- a-b
       else b <- b-a
  }
  return a

Ejercicio 7

Mostrar que el lenguaje ${\mathcal {S}}$ es minimal, en el sentido que ninguna de las instrucciones

V ← V + 1

,

V ← V - 1

y

IF V ≠ 0 GOTO A

pueden eliminarse del lenguaje sin perder expresividad.

Solución

Pistas:

• Para la primera probar por inducción que no importa las instrucciones que ponga el valor de salida siempre será 0.
• Para la segunda no se me ocurre en este momento.
• Para la tercera probar que cualquier función que haga va a estar acotada por el tamaño del programa asi que f(x) = x no puede hacerse (por ejemplo).

Ejercicio 8

Sean $g:I\!\!N^{n+1}\to I\!\!N,s,t:I\!\!N\to I\!\!N$ funciones computables. Usando las macros vistas en clase, escribir programas que computen las siguientes funciones:

Ítem a

$f_{1}(x_{1},\dots ,x_{n},y)={\mbox{max}}\{g(x_{1},\dots ,x_{n},i):0\leq i\leq y\}$

Solución

[A1] Z2 ← g(X1, ..., Xn, Z1)
     Z3 ← Z2 < Y
     IF Z3 ≠ 0 GOTO A2
     Y ← Z2
[A2] Z1 ← Z1 + 1
     Z4 ← Z1 < Xn+1
     IF Z4 ≠ 0 GOTO A1

Ítem b

$f_{2}(x_{1},\dots ,x_{n},y)={\begin{cases}{\mbox{max}}\{g(x_{1},\dots ,x_{n},i):s(y)\leq i\leq t(y)\}&{\mbox{si }}s(y)\leq t(y)\\0&{\mbox{sino}}\\\end{cases}}$

Solución

     Z1 ← s(Xn+1)
     Z5 ← t(Xn+1)
     Z6 ← Z1 > Z5
     IF Z6 ≠ 0 GOTO E
[A1] Z2 ← g(X1, ..., Xn, Z1)
     Z3 ← Z2 < Y
     IF Z3 ≠ 0 GOTO A2
     Y ← Z2
[A2] Z1 ← Z1 + 1
     Z4 ← Z1 < Z5
     IF Z4 ≠ 0 GOTO A1

Ejercicio Extra 1

Si $f,g_{1},\dots ,g_{k}\,\!$ son computables con $Dom(f)\subseteq I\!\!N^{k}$ y $Dom(g_{i})\subseteq I\!\!N^{r}$ para todo $i\in \{1,\dots ,k\}$, entonces la composición $h\,\!$ es computable:

$h(x_{1},\dots ,x_{r})=f(g_{1}(x_{1},\dots ,x_{r}),\dots ,g_{k}(x_{1},\dots ,x_{r}))\,\!$.

¿Cuál es el dominio de $h\,\!$?

Nota: hay un pequeño error en el enunciado, $h\,\!$ es computable sólo si

$Dom(f)\supseteq Img(g_{1})\times \dots \times Img(g_{k})$

Solución

$Dom(h)=\bigcap _{0<i\leq k}Dom(g_{1})$