Obligatorio 2

1) Ejercicio 3 de las notas 2.

2) Indicar el programa que tiene la codificación 50*3^36.

3) Dar la codificación numérica del siguiente programa P:

   PROGRAM(X0)
       WHILE (X0 NOT = 0) DO
           ASSIGN(X0,PRED(X0))
       END
   RESULT(X0)

4) Demostrar que no existe un programa P que pueda decidir si dos
   programas P arbitrarios computan la misma función.

5) ¿Son computables las siguientes funciones? Demostrar.

   a) K(n) = 1 si <Ix(n),n>  converge
             indef. en caso contrario

   b) cstop(p,n) = 1 si <Ix(p),n> diverge
                   indef. en caso contrario

6) Sea g(n) = n + 1.

   Cuáles de los conjuntos son recursivamente enumerables?

   a) { q en N / Φq (q) = 0 }
   b) { q en N / Φq ≠ g }
   c) { q en N / Φq = g }

7) Probar que el problema 3-SAT es NP-completo, sabiendo que el
   problema SAT es NP-completo.

   a) K(n) = 1 si <Ix(n),n>  converge
             indef. en caso contrario

   b) cstop(p,n) = 1 si <Ix(p),n> diverge
                   indef. en caso contrario