Práctica1

Vista previa del material en texto

Lógica y Computabilidad
Práctica 1: Funciones primitivas recursivas y clases PRC
2do cuatrimestre 2022
Ejercicio 1
Para construir una constante k, aplicamos la función s (sucesor) unas k veces, partiendo inicialmente de la función n que
nos devuelve el 0.
fpxq “ k “ ps ˝ ¨ ¨ ¨ ˝ s
loooomoooon
k veces
˝ nqpxq “ skpnpxqq
Ejercicio 2
f1px, yq “ sumapx, yq “ x` y
sumapx, 0q “ u11pxq “ x
sumapx, y ` 1q “ gpsumapx, yq, x, yq donde gpx1, x2, x3q “ spu
3
1px1, x2, x3qq
ñ sumapx, y ` 1q “ spsumapx, yqq
f2px, yq “ prodpx, yq “ x ¨ y
prodpx, 0q “ npxq “ 0
prodpx, y ` 1q “ gpprodpx, yq, x, yq donde gpx1, x2, x3q “ sumapu
3
1px1, x2, x3q, u
3
2px1, x2, x3qq
ñ prodpx, y ` 1q “ sumapprodpx, yq, xq
f3px, yq “ potpx, yq “ x
y
potpx, 0q “ spnpxqq “ 1
potpx, y ` 1q “ gppotpx, yq, x, yq donde gpx1, x2, x3q “ prodpu
3
1px1, x2, x3q, u
3
2px1, x2, x3qq
ñ potpx, y ` 1q “ prodppotpx, yq, xq
f4px, yq “ x
x.
.x
loomoon
y veces
f4px, 0q “ 1
f4px, y ` 1q “ gpf4px, yq, x, yq donde gpx1, x2, x3q “ potpu
3
2px1, x2, x3q, u
3
1px1, x2, x3qq
ñ f4px, y ` 1q “ potpx, f4px, yqq
Esta función a veces se la llama “Power Tower” (Wikipedia)
g1pxq “ predpxq “ x´ 1
predp0q “ npq “ 0 Permitimos utilizar la función nula n sin parámetros.
predpx` 1q “ gppredpxq, xq donde gpx1, x2q “ u
2
2px1, x2q “ x2
ñ predpx` 1q “ x
g2px, yq “ restapx, yq “ x´ y
restapx, 0q “ u11pxq “ x
restapx, y ` 1q “ gprestapx, yq, x, yq donde gpx1, x2, x3q “ predpu
3
1px1, x2, x3qq
ñ restapx, y ` 1q “ predprestapx, yqq
1
https://en.wikipedia.org/wiki/Tetration#Terminology
g3px, yq “ maxtx, yu
g3px, yq “ sumaprestapx, yq, yq “ px´ yq ` y
Si x ě y, entonces g3 simplemente resta y suma y a un x que es más grande, y en efecto terminamos con x que era el
máximo. En el otro caso x ă y, al hacer la resta en N obtenemos x´ y “ 0, luego al sumar y obtenemos nuevamente
y que era el máximo.
g4px, yq “ mintx, yu
g4px, yq “ restapsumapx, yq,maxtx, yuq “ x` y ´maxtx, yu
Ejercicio 3
a)
Para la ida pñq hacemos una demostración por inducción estructural. Primero probamos que todas las funciones iniciales
(que están en Cc) cumplen la propiedad.
Función nula
fpxq “ npxq “ 0. La función nula cae en el caso fpxq “ k donde k “ 0.
Función sucesor
fpxq “ spxq “ x` 1. La función sucesor cae en el caso fpxq “ x` k donde k “ 1.
Función proyector
fpx1, . . . , xnq “ u
n
i px1, . . . , xnq “ xi. La función proyector cae en el caso fpx1, . . . , xnq “ xi ` k donde k “ 0.
Paso inductivo. Supongamos que existen f, g1, . . . , gm P Cc que cumplen con la propiedad. Como la única operación en Cc es la
composición, esa es la única forma de generar nuevas funciones. Probemos entonces que la función generada por composición
hpx1, . . . , xnq “ fpg1px1, . . . , xnq, . . . , gmpx1, . . . , xnqq P Cc también cumple con la propiedad.
Miremos todos los posibles casos para f que ya sabemos que cumple con la propiedad por hipótesis inductiva.
fpg1px1, . . . , xnq, . . . , gmpx1, . . . , xnqq “ k ñ hpx1, . . . , xnq “ k
fpg1px1, . . . , xnq, . . . , gmpx1, . . . , xnqq “ gjpx1, . . . , xnq ` k0 para algún j | 1 ď j ď m.
Por hipótesis inductiva, gj P Cc cumple con la propiedad. Por lo tanto gjpx1, . . . , xnq “ kj o bien gjpx1, . . . , xnq “ xi`kj
para algún i | 1 ď i ď n. Observar que necesitamos identificar kj con un sub́ındice ya que cada gj puede tener constantes
arbitrarias. Además, necesitamos usar un sub́ındice distinto para el xi ya que sino estaŕıamos limitando qué parámetro
de entrada puede usar cada gj .
• gjpx1, . . . , xnq “ kj ñ hpx1, . . . , xnq “ kj ` k0 “ k
• gjpx1, . . . , xnq “ xi ` kj ñ hpx1, . . . , xnq “ xi ` kj ` k0 “ xi ` k
Probamos entonces que cualquier función hpx1, . . . , xnq “ fpg1px1, . . . , xnq, . . . , gmpx1, . . . , xnqq P Cc cumple con la propiedad.
Es decir, vale que si h P Cc ñ hpx1, . . . , xnq “ k o bien hpx1, . . . , xnq “ xi ` k.
Para la vuelta pðq mostramos que podemos construir cualquier fpx1, . . . , xnq “ k o fpx1, . . . , xnq “ xi ` k a partir de
composición de las funciones iniciales, y por lo tanto f P Cc.
fpx1, . . . , xnq “ k “ s
kpnpxiqq para cualquier i
fpx1, . . . , xnq “ xi ` k “ s
kpuni px1, . . . , xnqq
b)
En el ejercicio 2 vimos que la función sumapx, yq “ x` y es p.r. pero suma R Cc pues no cumple con la propiedad.
2
Ejercicio 4
Cualquier clase PRC contiene las funciones iniciales y está cerrada por recursión primitiva y composición. Para mostrar que
los predicados están en cualquier clase PRC, es suficiente con mostrar que se pueden construir a partir de las funciones
iniciales utilizando recursión primitiva y/o composición.
Para simplificar la escritura vamos a utilizar la función αpxq la cual es PR a partir de las iniciales y por lo tanto pertenece
a cualquier clase PRC.
αpxq “
#
1 si x “ 0
0 si no
Además, podemos definir el predicado pxq “ αpxq que niega otro predicado.
ď) ppx, yq “
#
1 si x ď y
0 si no
“ αpx´ yq
ě) ppx, yq “
#
1 si x ě y
0 si no
“ αpy ´ xq
“) ppx, yq “
#
1 si x “ y
0 si no
“ px ď yq ¨ px ě yq
‰) ppx, yq “
#
1 si x ‰ y
0 si no
“ px “ yq
ă) ppx, yq “
#
1 si x ă y
0 si no
“ px ě yq
ą) ppx, yq “
#
1 si x ą y
0 si no
“ px ď yq
Ejercicio 5
Podemos escribir h de la siguiente forma equivalente en donde se puede ver más claramente que es composición de funciones,
en particular es composición de funciones en C pues todas las fi y g están en C. Como C es una clase PRC resulta que h P C.
hpx1, . . . , xnq “
řk
i“1 fipx1, . . . , xnq ¨ pipx1, . . . , xnq ` gpx1, . . . , xnq ¨ p
řk
i“1 pipx1, . . . , xnqq
También podemos analizarlo por casos:
Caso 1: D!i : N, 1 ď i ď k tal que pipx1, . . . , xnq es verdadero.
Observemos que si existe i, tiene que ser único pues todos los predicados p1, . . . , pk son disjuntos. Luego, vale que hpx1, . . . , xnq “
fipx1, . . . , xnq por definición (el predicado pipx1, . . . , xnq es verdadero y por lo tanto “selecciona” el caso de fi dentro de la
definición de h). Como todas las fi P C por hipótesis ñ h P C.
Caso 2: @i : N, 1 ď i ď k ñ pipx1, . . . , xnq es falso.
Como no existe predicado pi que resulte verdadero, por definición h “selecciona” el último caso “si no” y luego resulta
hpx1, . . . , xnq “ gpx1, . . . , xnq. Como g P C por hipótesis ñ h P C.
Ejercicio 6
Una clase de funciones C es PRC si contiene las funciones iniciales y está cerrada por composición y recursión primitiva.
Podemos afirmar que una función cualquiera va a estar en toda clase PRC si podemos demostrar que pertenece a la clase
3
PR. La clase PR es la clase PRC más “chica”, son todas las funciones que se pueden construir a partir de las funciones
iniciales mediante composición y/o recursión primitiva, y por lo tanto van a pertenecer a cualquier clase PRC.
No obstante, una clase C puede ser PRC y a su vez contener funciones que no puedan ser construidas a partir de las iniciales.
Esto sucede cuando la clase incluye expĺıcitamente alguna función adicional que no pertenece a la clase PR. En esencia, para
generar nuevas funciones dentro de esta clase C, además de tener las 3 funciones iniciales, tendŕıamos esta función adicional.
a)
parpxq “
#
1 si x es par
0 si no
parp0q “ 1
parpx` 1q “ gpparpxq, xq donde gpx1, x2q “ u
2
1px1, x2q ñ parpx` 1q “ parpxq
Definimos imparpxq “ parpxq para usar en los siguientes items.
b)
fpxq “ div2pxq “ tx{2u
div2p0q “ 0
div2px` 1q “
#
div2pxq si parpxq
spdiv2pxqq si no
“ div2pxq ¨ parpxq ` spdiv2pxqq ¨ imparpxq
c)
hpx1, . . . , xn, tq “
$
’
&
’
%
fpx1, . . . , xnq si t “ 0
g1px1, . . . , xn, k, hpx1, . . . , xn, t´ 1qq si t “ 2 ¨ k ` 1
g2px1, . . . , xn, k, hpx1, . . . , xn, t´ 1qq si t “ 2 ¨ k ` 2
Planteamos el caso base del esquema de recursión primitiva para h. Notar que si t “ 0 siempre entramos en el primer caso
de h pues no existe k P N para satisfacer los otros 2 casos cuando t “ 0.
hpx1, . . . , xn, 0q “ fpx1, . . . , xnq
Para el caso t ą 0 primero reescribimos la función por casoscolocando t`1 en donde antes teńıamos t para poder ajustarnos
al esquema de recursión primitiva.
hpx1, . . . , xn, t` 1q “
#
g1px1, . . . , xn, k, hpx1, . . . , xn, t` 1´ 1qq si t` 1 “ 2 ¨ k ` 1
g2px1, . . . , xn, k, hpx1, . . . , xn, t` 1´ 1qq si t` 1 “ 2 ¨ k ` 2
“
#
g1px1, . . . , xn, k, hpx1, . . . , xn, tqq si t “ 2 ¨ k
g2px1, . . . , xn, k, hpx1, . . . , xn, tqq si t “ 2 ¨ k ` 1
Ahora necesitamos despejar k en función de t.
t “ 2 ¨ k ñ k “ tt{2u “ div2ptq
t “ 2 ¨ k ` 1 ñ k “ tpt´ 1q{2u “ div2pt´ 1q “ div2ptq pues t es impar y div2 redondea hacia abajo
Reescribimos h eliminando por completo la k.
hpx1, . . . , xn, t` 1q “
#
g1px1, . . . , xn,div2ptq, hpx1, . . . , xn, tqq si parptq
g2px1, . . . , xn,div2ptq, hpx1, . . . , xn, tqq si imparptq
También podemos escribir h como suma de cada caso por su predicado.
4
hpx1, . . . , xn, t` 1q “ g1px1, . . . , xn,div2ptq, hpx1, . . . , xn, tqq ¨ parptq ` g2px1, . . . , xn,div2ptq, hpx1, . . . , xn, tqq ¨ imparptq
Conclusión
h sigue el esquema de recursión primitiva.
h compone funciones que están en C (puntualmente f , g1 y g2).
h compone funciones que están en toda clase PRC (puntualmente div2, par, impar).
C es una clase PRC por el enunciado, entonces contiene a las funciones div2, par, impar.
Por lo tanto cualquier h que cumpla con este esquema pertenece a C.
Ejercicio 7
Usamos la notación x “ x1, . . . , xn para simplificar la escritura. Ya vimos en la teórica que los operadores acotados están
necesariamente acotados por arriba. La idea de este ejercicio es mostrar que también podemos acotarlos por abajo.
cantidadppx, y, zq “
řz
t“0 ppx, tq ¨ pt ě yq “
řz
t“y ppx, tq
todosppx, y, zq “ p@tqďz pppx, tq ¨ pt ě yq ` pt ă yqq “ p@tqyďtďz ppx, tq
Otra forma: todosppx, y, zq “ cantidadppx, y, zq “ z ´ y
algunoppx, y, zq “ pDtqďz pppx, tq ¨ pt ě yq ` pt ă yqq “ pDtqyďtďz ppx, tq
Otra forma: algunoppx, y, zq “ cantidadppx, y, zq ą 0
Recordemos la definición de la minimización acotada: mintďy ppx, tq “
řy
u“0
śu
t“0 αpppx, tqq
mı́nimoppx, y, zq “ mintďz pppx, tq ¨ pt ě yqq “ minyďtďz ppx, tq
Podemos definir el máximo utilizando el mı́nimo, agregando una condición adicional al predicado: que no exista ningún
otro t1 ą t para el cual también valga el predicado p. En esencia, buscamos primero el mı́nimo real, y si existe un t más
grande para el cual también vale el predicado, tenemos que seguir buscando el próximo mı́nimo a partir del encontrado,
y aśı hasta eventualmente llegar al máximo.
máximoppx, y, zq “ mı́nimoqpx, y, zq donde qpx, tq “ ppx, tq ¨ pDt
1qtăt1ďz ppx, t
1q
Sea m “ mı́nimoppx, y, zq, M “ máximoppx, y, zq
únicoppx, y, zq “ pm “Mq ¨m` pm ‰Mq ¨ pz ` 1q
Ejercicio 8
cocientepx, yq “ mintďx ppt ¨ y ` r “ xq ^ p0 ď r ă yqq
restopx, yq “ x´ cocientepx, yq ¨ y
dividepx, yq “ restopx, yq “ 0
primopxq “ pDtq1ătăx dividepx, tq
ráızpx, yq “ mintďy pt` 1q
x ą y
nprimop0q “ 0
nprimopn` 1q “ mintďc pprimoptq ^ t ą nprimopnqq
Donde c “ nprimopnq!` 1 funciona como cota porque nprimopn` 1q ď nprimopnq!` 1 (justificado en la teórica).
5
Ejercicio 9
Sea xx, yy “ 2xp2y ` 1q ´ 1 la codificación de pares de naturales. Esta función es p.r. pues es una composición de otras
funciones p.r. como la potencia, multiplicación y suma.
Esta codificación es una biyección, pues hay una única solución px, yq a la ecuación z “ xx, yy. Notemos que para garantizar
esto es necesario restar 1 en la codificación, pues sino el par x0, 0y “ 1 y luego sucedeŕıa que xx, yy ě 1 @x, y P N.
z “ xx, yy “ 2xp2y ` 1q´ 1 ðñ z ` 1 “ 2xp2y ` 1q
Observemos que 2x es siempre un número par o 1 (en el caso x “ 0), mientras que 2y ` 1 es siempre un número impar. Por
lo tanto, dado z podemos volver a obtener el par px, yq realizando 2 pasos.
1. x “ maxxďz 2
x|pz ` 1q
2. y “ p z`12x ´ 1q{2
Definimos los observadores l (left) y r (right) del par z “ xx, yy tal que:
lpzq “ minxďz ppDyqďz z “ xx, yyq
rpzq “ minyďz ppDxqďz z “ xx, yyq
Como la codificación de pares y los observadores son p.r. podemos concluir que toda clase PRC los contiene.
Ejercicio 10
Para demostrar que la función de Fibonacci está en toda clase PRC vamos a mostrar que podemos definirla como una función
primitiva recursiva.
Sea f : NÑ N la función de Fibonacci tal que:
fp0q “ 0
fp1q “ 1
fpn` 2q “ fpn` 1q ` fpnq
Esta definición difiere del esquema de recursión primitiva por 2 razones: tenemos 2 casos bases y necesitamos mirar los 2
resultados anteriores en el paso recursivo.
¿Acaso no tenemos ya una forma de codificar 2 valores como un único número? Intentemos definir Fibonacci con una nueva
función g utilizando la codificación de pares. Para cualquier n P N, gpnq nos devuelve un par codificado con los términos n y
n` 1 de Fibonacci.
gp0q “ x0, 1y
gpn` 1q “ xrpgpnqq, lpgpnqq ` rpgpnqqy
La función g es p.r. pues sigue el esquema de recursión primitiva y es composición de funciones p.r.
Finalmente, podemos redefinir f en función de g de la siguiente forma: fpnq “ lpgpnqq. Por lo tanto, f es p.r. y consecuente-
mente pertenece a cualquier clase PRC.
Ejercicio 11
Definimos una función H que va a realizar la recursión mutua codificándola en un par.
Hpx, tq “ xh1px, tq, h2px, tqy
6
Planteamos el esquema de recursión primitiva.
Hpx, 0q “ xh1px, 0q, h2px, 0qy “ xf1pxq, f2pxqy
Hpx, t` 1q “ xh1px, t` 1q, h2px, t` 1qy
“ xg1ph1px, tq, h2px, tq, x, tq, g2ph2px, tq, h1px, tq, x, tqy
“ xg1plpHpx, tqq, rpHpx, tqq, x, tq, g2prpHpx, tqq, lpHpx, tqq, x, tqy
H sigue el esquema de recursión primitiva y es composiciones de funciones p.r. y de f1, f2, g1, g2 P C ñ H P C.
Como H P C está codificando a h1 y h2 de la siguiente forma:
h1px, tq “ lpHpx, tqq
h2px, tq “ rpHpx, tqq
ñ h1, h2 P C.
Ejercicio 12
Pendiente
Ejercicio 13
a)
Por el Teorema Fundamental de la Aritmética, todos los números naturales mayores a 1 tienen una única factorización como
producto de números primos. La codificación de una secuencia es simplemente interpretar todos los elementos de ella como
las potencias de los números primos de la factorización de algún número natural.
Como el TFA nos dice que esta factorización es única, y como solo consideramos secuencias finitas que no terminan en cero,
efectivamente tenemos una biyección entre los números naturales y las secuencias al utilizar esta codificación.
Notemos que no podemos permitir que haya 0s al final de la secuencia pues sino rompemos la biyección, ya que tendŕıamos
infinitas secuencias que codifican al mismo número.
Nos quedaron afuera el 0 y el 1 (el TFA solo vale para números naturales mayores a 1). No existe secuencia que codifique
a 0, pero esto no es problema pues el enunciado pide una biyección con los naturales mayores a 0. Y por otro lado, veamos
que la secuencia vaćıa rs codifica a 1 pues resulta una productoria vaćıa.
b)
La secuencia vaćıa codifica al 1. Si n es el tamaño de la secuencia, entonces la secuencia vaćıa rs tiene n “ 0, y por lo tanto:
rs “
śn
i“1 nprimopiq
ai “
ś0
i“1 nprimopiq
ai “ 1
Definimos las funciones a partir de otras funciones que ya mostramos que están en toda clase PRC:
|s| “ maxiďs dividepnprimopiq, sq
sris “ maxjďs dividepnprimopiq
j , sq
rxs “ nprimop1qx “ 2x
r ˝ s “ r ¨
ś|s|
i“1 nprimop|r| ` iq
sris
subps, i, jq “
śj
k“i nprimopk ´ iq
sris
7
c)
Ejercicio 14
Pendiente
Ejercicio 15
Pendiente
8