Resolucion final del 05/03/20 (Lógica y Computabilidad)

Ejercicio 1

I. A infinito y ce ==> existe f computable y creciente tq f(N) = A

Falso. Si exisitiera tal f computable y creciente, decidir la no pertenencia de un elemento al conjunto A podría lograrse por ej usando búsqueda binaria sobre la imagen de f. Luego A sería co-ce y por lo tanto computable, sin embargo ce no implica computable (por ejemplo el conjunto K es ce y no computable). Entonces no debe existir f computable y creciente tq f(N) = A. (Por otro lado, sí existen función computables tq A = {g(0), g(1), … }, pero no necesariamente es creciente, así como una función creciente h que no necesariamente será computable)

II. f computable ==> Ui Wf(i) es ce

Verdadero. Wn = {x: fi sub n (x) termina} = el dominio del n-ésimo programa. Sabemos que Wn es ce. Para ver que además Ui Wf(i) lo es, podemos ver el siguiente programa:

for (i )

for (j<i)

if STP(X, f(j), i ) = 1 goto E

De esta forma, dado un X, buscamos si pertenece al dominio de cada programa de número f(j) “en paralelo”. Bast con que esté en el dominio de alguno de ellos para que pertenezca al conjunto. (Si bien el programa dado no está en S, tiene poder de cómputo equivalente).

Ejercicio 2

A conjunto ce. El elemento e pertenece a A ==> fi e es total. Quiero probar que exite e tq fi e es total =/=> e pertenece a A.

Esto se debe a que si se diera la negación, e pertenece a A <==> fi e es total, luego A = Tot, que es un conjunto no ce. Veamos la prueba.

Supongamos que Tot es ce. Luego existe f computable tq Tot={f(0), f(1), … }. Entonces debe existir e tq Fi e (x) = Fi f(x) (x) + 1, que es computable y total ya que f lo es. Luego e pertenece a Tot. Por lo tanto debe existir además un elemento u tal que f(u) = e ==> Fi f(u) (x) = Fi f(x) (x) + 1. En este caso u es fijo pero x variable, tomando u = x llegamos a un absurdo que viene de suponer que Tot es ce.

Ejercicio 4

I. Qvq el conjunto de fórmulas de primer orden satisfacibles en algún modelo finito es ce. Dado un modelo finito, la cantidad de valuaciones del modelo también resulta finita, por lo que recorrerlas todas es factible (de hecho, forman un conjunto computable). Luego dada una fórmula Fi puedo decidir si es satisfacible en dicho modelo viendo para cada valuación v si v |= Fi, y terminando cuando esto ocurra. Este modelo se encuentra recorriendo todos los modelos finitos.

II. Qvq el conjunto de sentencias de primer orden verdaderas en todo modelo finito es co-ce Para ver que una sentencia Fi dada no pertenece al conjunto de de sentencias verdaderas en todo modelo finito basta con verificar que es inválida en alguno. Es decir que recorriendo todos los modelos finitos (lo cual es posible gracias a que L admite codificación, y por más que haya una cantidad infinita de ellos), el programa termina al encontrar el primer modelo que invalida Fi. Aún si este modelo invalidante fuera único, sería alcanzado en algún momento.