Final del 11/08/21 (Lógica y Computabilidad)

Aclaración

El examen consistió de 2 partes. En una parte se evaluó la parte de Lógica, y en otro la de Computabilidad. En ambas partes, el profesor le permitió al comienzo elegir un tema al alumno para que cuente, y luego se le hicieron preguntas relacionadas (si estuviste estudiando, te das cuenta que tarde o temprano todo se relaciona con todo... así que cuidado). Luego da un ejercicio que es más de pensar y aplicar los contenidos estudiados.

Por lo tanto, podemos pensar el oral de la siguiente manera. Paso a comentar en primera persona.

Ejercicio 1 (Lógica)

Tema a elección + preguntas relacionadas

Ejercicio 2 (Lógica)

En particular en este ejercicio me tomó un ejercicio parecido al "Busy Beaver". Acá la idea era que dada una función que me devolviera el nº de programa de longitud l que termina con entrada x, probar si esta era o no computable. El secreto estaba en probar que si esto funcionara, estaríamos probando el Halting Problem.

Ejercicio 3 (Computabilidad)

Tema a elección + preguntas relacionadas

Ejercicio 4 (Computabilidad)

Acá me tomó dos sub-ejercicios.

a) Dado un lenguaje $L$ con igualdad probar que existe un conjunto Γ de sentencias del lenguaje $L$ tal que A como modelo: $A|=$ Γ $\leftrightarrow$ A tiene universo infinito

b) ¿Existe una fórmula/sentencia tal que $A|=$ ϕ $\leftrightarrow$ A tiene universo infinito?