Final Flashcards
¿Qué dice el teorema de incompletitud de Gödel?
Ningún sistema axiomático capaz de describir los números naturales y la aritmética con suficiente expresividad es a la vez consistente y completa
¿Qué es una máquina de Turing?
Una máquina de Turing es un modelo matemático de computación que consiste en una cinta infinita dividida en celdas, una cabeza lectora/escritora que se mueve a lo largo de la cinta, y una tabla de reglas que determina sus acciones basadas en el estado actual y el símbolo leído en la cinta. Es utilizada para formalizar el concepto de algoritmo y computabilidad, demostrando que cualquier cálculo realizable por una computadora puede ser simulado por una máquina de Turing.
¿Qué significa que una máquina de Turing sea determinística o no?
Una máquina de Turing determinística (MTD) es aquella en la que, para cada combinación de estado actual y símbolo leído, existe una única acción definida (movimiento de la cabeza, cambio de estado, escritura en la cinta). Esto significa que su comportamiento está completamente determinado y predecible.
Una máquina de Turing no determinística (MTND) permite múltiples posibles acciones para una misma combinación de estado y símbolo leído. En cada paso, puede “elegir” entre varias opciones, lo que le permite explorar múltiples caminos simultáneamente. Esta característica se utiliza teóricamente para analizar problemas de complejidad y decidir la existencia de soluciones, aunque no corresponde a ninguna implementación física directa.
¿Qué es una función parcial?
Función parcial: Una función parcial es una función que no está definida para todos los posibles valores de entrada de su dominio. Es decir, hay algunos valores de entrada para los cuales la función no produce ningún resultado.
Función total: Una función total es una función que está definida para todos los posibles valores de entrada de su dominio. Esto significa que, para cualquier valor de entrada, la función siempre produce un resultado.
¿Qué significa que una función sea Turing computable?
Una función es Turing computable si existe una máquina de Turing que puede calcular el valor de la función para cualquier entrada válida en un número finito de pasos. En otras palabras, si para cualquier entrada dada, la máquina de Turing sigue sus reglas y produce el resultado correcto de la función o determina que no hay resultado, entonces la función es considerada Turing computable. Esto formaliza la idea de que la función puede ser calculada mediante un algoritmo efectivo.
¿Cómo es el esquema de recursión primitiva?
El esquema de recursión primitiva es un método para definir funciones recursivas de manera estructurada y controlada. Se compone de tres reglas básicas:
Base: Especifica valores iniciales para las variables de la función.
Recursión: Define cómo calcular el valor de la función para valores sucesivos, utilizando el valor calculado inmediatamente anterior.
Composición: Permite la composición de funciones previamente definidas dentro de la recursión, facilitando la creación de funciones más complejas a partir de funciones simples.
Este esquema es más limitado que la recursión general, ya que no permite la recursión mutua ni la definición de funciones que se llamen a sí mismas de manera directa.
¿Qué es una clase de funciones PRC?
Una clase de funciones PRC (Primitive Recursive Class) se refiere al conjunto de funciones que pueden ser definidas utilizando el esquema de recursión primitiva. Estas funciones son computables por una máquina de Turing y se caracterizan por su capacidad de ser definidas de manera estructurada y limitada, utilizando operaciones básicas como la composición, la proyección y la recursión primitiva.
La clase de funciones totales Turing computables es una clase PRC
¿Qué es una función primitiva recursiva?
Una función primitiva recursiva es una función matemática que puede ser definida utilizando el esquema de recursión primitiva.
Una función es primitiva recursiva sii pertenece a toda clase PRC
Demostrar que una función es p.r. sii pertenece a toda clase PRC
<=) La clase de funciones p.r. es una clase PRC. Luego, si f pertenece a toda clase PRC, en particular f es p.r.
=>) Sea f p.r. y sea C una clase PRC. Como f es p.r., hay una lista f1,f2,…,fn tal que
- f = fn
- fi es inicial (luego está en C) o se obtiene por composición o recursión primitiva a partir de funciones fj (j < i) (luego también está en C)
Entonces todas las funciones de la lista están en C (por inducción). En particular, fn está en C.
La clase de funciones p.r. es la clase PRC más chica
¿Qué es un estado?
Un estado de un programa P es una lista de ecuaciones de la forma V = m (donde V es una variable y m es un número) tal que:
- hay una ecuación para cada variable que se usa en P
- no hay dos ecuaciones para la misma variable
¿Qué es una descripción instantánea?
Una descripción instantánea es un par (i, σ) donde:
- 1 <= i <= n + 1 (n longitud del programa)
- σ es un estado
Si i = n + 1, se llama terminal
¿Qué es un cómputo?
Un cómputo de un programa P a partir de una descripción instantánea d1 es una lista:
d1, d2, …, dk
de descripciones instantáneas de P tal que:
- di+1 es sucesor de di
- dk es terminal
El cómputo a partir de un estado inicial se denota Ψ_p^m
¿Qué es una función parcial computable?
Una función es parcial computable si existe un programa P tal que:
f(r1,…,rm) = Ψ_P^m(r1,…,rm)
¿Qué es el teorema de Cantor?
El conjunto de las funciones totales N –> N no es numerable
Demostración.
Supongamos que lo fuera. Las enumero: f₀, f₁ …
valores de f₀: f₀(0) f₀(1) …
valores de f₁: f₁(0) f₁(1) …
…
valores de fₖ: fₖ(0) fₖ(1) …
Defino la siguiente función:
g(x) = fₓ(x) + 1
Enunciar y demostrar que HALT no es computable
HALT(x,y) es verdadero sii el programa con número y y entrada x no se indefine.
HALT(x,y) = 1 si Ψₚ⁽¹⁾ (x) ⭣
HALT(x,y) = 0 si no
donde P es el único programa tal que #(P) = y
Demostración:
Supongamos que HALT es computable.
Construimos el siguiente programa:
[A] IF HALT(X,X) = 1 GOTO A
Supongamos que #(Q) = e. Entonces
ΨQ(x) = ⭡ si HALT(x,x) = 1
ΨQ(x) = 0 si no
Entonces
HALT(x, e) = 1 sii ΨQ(x) ⭣ sii HALT(x,x) ≠ 1
Llegamos al absurdo si x = e
Describir el proceso de diagonalización
- Sea Pi el programa con número i
- Supongo que P es computable
- Defino una función f computable
- f(x) ⭣ sii Ψₚ(x) ⭡
¿Primitiva recursiva = Computable?
No, no son lo mismo.
p.r. implica computable.
Computable no implica p.r.
Por ejemplo, la función de Ackermann es computable pero no p.r.
A(m,n) = n + 1 si m = 0
A(m,n) = A(m-1,1) si m > 0 y n = 0
A(m,n) = A(m-1, A(m,n-1)) si no
Enunciar y demostrar el teorema de Rice
A ⊆ N es un conjunto de índices si existe una clase de funciones N → N parciales computables C tal que A = {x : Φx ∈ C}
Si A es un conjunto de índices tal que ∅ ≠ A ≠ N, A no es computable
Demostración:
Supongamos C tal que A = {x: ϕx ∈ C} computable. Sean f ∈ C y g ∉ C funciones parciales computables.
Sea h: N² → N la siguiente función parcial computable:
h(t,x) = g(x) si t ∈ A
h(t,x) = f(x) si no
Por el Teorema de la Recursión, existe e tal que ϕe(x) = h(e,x).
Si e ∈ A ⇒ ϕe = g ⇒ ϕe ∉ C ⇒ e ∉ A Absurdo
Si e ∉ A ⇒ ϕe = f ⇒ ϕe ∈ C ⇒ e ∈ A Absurdo
Enunciar y demostrar el teorema de la recursión
El teorema de la recursión, también conocido como el teorema del punto fijo de Kleene, es un resultado fundamental en la teoría de la computabilidad. Este teorema afirma que para cualquier función computable, existe un programa que genera una salida equivalente a la salida de la función aplicada al propio programa.
Para cualquier función computable ( f ), existe un índice ( e ) tal que el programa con índice ( e ) produce la misma salida que el programa con índice ( f(e) ).
Formalmente:
\forall f: N -> N, \exists e tal que \varphi_e = \varphi_{f(e)}
donde ( \varphi_e ) denota la función computable con índice ( e ).
La demostración se basa en la existencia de un “quiner” o un programa que se auto-reproduce.
- Definición de un Quiner: Un programa ( Q ) es un quiner si, cuando se ejecuta, produce una copia de su propio código como salida.
-
Construcción del Programa Recursivo:
- Sea ( f ) una función computable. Queremos encontrar un programa ( e ) tal que el comportamiento de ( e ) sea equivalente a ( f(e) ).
- Consideremos una función ( s ) que toma como entrada un índice de programa ( e ) y produce un programa que, cuando se ejecuta, simula la ejecución de ( f(e) ). Formalmente, ( s(e) ) es un índice para el programa que computa ( \varphi_{f(e)} ).
-
Existencia del Índice ( e ):
- Por el teorema de s-m-n (teorema de parametrización), sabemos que existe una función computable ( g ) tal que ( g(e) ) es un índice para un programa que computa ( \varphi_{f(e)} ).
- Ahora, definimos una función ( q ) tal que ( q(x) = f(g(x)) ).
- Según el teorema del punto fijo, existe un índice ( e ) tal que ( \varphi_e = \varphi_{q(e)} ).
-
Conclusión:
- Este índice ( e ) es el que buscábamos, ya que ( \varphi_e = \varphi_{q(e)} = \varphi_{f(g(e))} ).
- Dado que ( g(e) ) es simplemente una reparametrización que no altera la función computada, podemos escribir ( g(e) = e ), obteniendo así ( \varphi_e = \varphi_{f(e)} ).
Por lo tanto, hemos demostrado que para cualquier función computable ( f ), existe un programa con índice ( e ) tal que el programa computa ( f(e) ), satisfaciendo así el teorema de la recursión.
¿Qué es el teorema del parámetro?
Para un lenguaje de programación dado y números enteros positivos m y n, existe un algoritmo particular que acepta como entrada el código fuente de un programa con m + n variables libres, junto con m valores. Este algoritmo genera código fuente que sustituye efectivamente los valores de las primeras m variables libres, dejando el resto de las variables libres.
Hay un programa Px2 para la función fx2(x1) = f (x1, x2).
La transformación (x2, #(P)) 7→ #(Px2) es p.r., es decir, existe una función S : N2 → N p.r. tal que dado x2 e y = #(P) calcula #(Px2)
Enunciar y demostrar el lema de Lindenbaum
Γ ⊆ FORM es maximal consistente (m.c.) en SP si
- Γ es consistente y
- para toda fórmula ϕ
– ϕ ∈ Γ o
– existe ψ tal que Γ ∪ {ϕ} ⊢ ψ y Γ ∪ {ϕ} ⊢ ¬ψ
Lema
Si Γ ⊆ FORM es consistente, existe Γ’ m.c. tal que Γ ⊆ Γ’
Demostración:
Enumeramos todas las fórmulas: ϕ1, ϕ2, . . . Definimos
- Γ0 = Γ
- Γn+1 = Γn ∪ {ϕn+1} si Γn ∪ {ϕn+1} es consistente
- Γn+1 = Γn si no
- Γ’ = ∪i≥0 Γi
Tenemos
1. Γ’ ⊇ Γ
2. cada Γi es consistente
3. Γ’ es consistente
- si no, existe ψ tal que Γ’ ⊢ ψ y Γ’ ⊢ ¬ψ
- en ambas derivaciones aparecen únicamente {γ1, . . . , γk } ⊆ Γ’
- sea j suficientemente grande tal que {γ1, . . . , γk } ⊆ Γj
- entonces Γj ⊢ ψ y Γj ⊢ ¬ψ; contradice 2
4. Γ’ es maximal
- supongamos ϕ ∉ Γ’
- Debe existir n tal que ϕn+1 = ϕ
- ϕn+1 ∉ Γn+1, entonces Γn ∪ {ϕn+1} es inconsistente
- luego Γ’ ∪ {ϕn+1} es inconsistente (pues Γ’ ⊇ Γn)
Enunciar y demostrar el teorema de Compacidad (SP)
Sea Γ ⊆ FORM. Si todo subconjunto finito de Γ es satisfacible,
entonces Γ es satisfacible.
Demostración:
supongamos Γ insatisfacible
⇒ Γ es inconsistente
⇒ existe ψ tal que Γ ⊢ ψ y Γ ⊢ ¬ψ
⇒ se usan solo finitos axiomas de Γ
⇒ existe ∆ ⊆ Γ finito tal que ∆ ⊢ ψ y ∆ ⊢ ¬ψ
⇒ ∆ es inconsistente
⇒ ∆ es insatisfacible
Demostrar que la clase de funciones totales Turing computables (o computables en C, o en Java) es una clase PRC
Para demostrar que la clase de funciones totales Turing computables (o computables en C, o en Java) es una clase PRC, vamos a recordar primero algunos conceptos fundamentales:
Función Total Turing Computable (FTC): Una función
𝑓: 𝑁𝑘→𝑁 es total Turing computable si existe una máquina de Turing que para cualquier entrada 𝑥1,𝑥2,…,𝑥𝑘 en 𝑁, produce 𝑓(𝑥1,𝑥2,…,𝑥𝑘) y siempre termina (es decir, no se queda en un ciclo infinito).
Clase PRC (clase de funciones parciales recursivas cerradas): Una clase de funciones es PRC si está cerrada bajo las siguientes operaciones básicas:
Funciones primitivas recursivas: Incluyen funciones básicas como la función cero, la función sucesora, las funciones proyección, y están cerradas bajo la composición y la recursión primitiva.
Minimización (μ-recursión): La minimización de una función recursiva es otra función recursiva que encuentra el menor valor que hace que la función original sea cero.
Las funciones totales Turing computables son un subconjunto de las funciones parciales recursivas, pero con la garantía adicional de que están definidas para todas las entradas posibles. Vamos a demostrar que la clase de funciones totales Turing computables es una clase PRC:
Paso 1: Definir las Funciones Básicas
Funciones iniciales: Las funciones constantes (por ejemplo, 𝑓(𝑥) = 0), la función sucesora (𝑆(𝑥) = 𝑥+1), y las funciones proyección (𝑃𝑖𝑘(𝑥1,…,𝑥𝑘) = 𝑥𝑖) son todas Turing computables y primitivas recursivas.
Paso 2: Composición de Funciones
Composición: Si 𝑓 y 𝑔 son funciones Turing computables, entonces la composición ℎ(𝑥) = 𝑓(𝑔1(𝑥),𝑔2(𝑥),…,𝑔𝑚(𝑥)) también es Turing computable. Las máquinas de Turing para 𝑔𝑖 pueden computarse secuencialmente y luego pasar sus resultados a la máquina de Turing para 𝑓.
Paso 3: Recursión Primaria
Recursión Primaria: Si 𝑓 y 𝑔 son Turing computables, y ℎ se define por recursión primaria usando 𝑓 y 𝑔, entonces ℎ también es Turing computable. Esto sigue porque podemos construir una máquina de Turing que implemente el esquema recursivo directamente.
Demostrar que existen modelos de primer orden no estandar para la aritmetica (0, S, <, +, .)
Para demostrar la existencia de modelos no estándar de la aritmética de primer orden (usando los símbolos 0, 𝑆 (sucesor), < (menor que), + (suma) y ⋅ (multiplicación)), vamos a utilizar el Teorema de Compacidad. Este teorema es fundamental en lógica matemática y nos permite mostrar la existencia de modelos no estándar sin necesidad de recurrir a teorías adicionales.
Teorema de Compacidad (recordatorio):
Enunciado: Si cada subconjunto finito de un conjunto Γ de fórmulas de primer orden es satisfacible, entonces Γ es satisfacible.
Paso 1: Extender la Aritmética
Teniendo los axiomas que definen 0, el sucesor 𝑆, y las operaciones + y ⋅. Queremos demostrar que existen modelos de estos axiomas que no sean isomorfos al modelo estándar 𝑁.
Para hacerlo, consideremos la aritmética extendida con una nueva constante 𝑐, y agreguemos una serie de axiomas que implican que 𝑐 es mayor que cualquier número natural estándar:
Γ = {Axiomas} ∪ {𝑐 > 0, 𝑐 > 1, 𝑐 > 2,…}
Paso 2: Verificar la Satisfacibilidad de Subconjuntos Finitos
Para aplicar el Teorema de Compacidad, necesitamos verificar que cada subconjunto finito de Γ es satisfacible. Consideremos un subconjunto finito de Γ
Γ: Δ = {Axiomas} ∪ {𝑐 > 0, 𝑐 > 1,…, 𝑐 > 𝑛}
donde 𝑛 es un número natural arbitrario. Podemos construir un modelo para Δ de la siguiente manera:
Tomamos el modelo estándar 𝑁 para los números naturales.
Extendemos 𝑁 agregando un nuevo elemento 𝑐 tal que 𝑐 sea mayor que cualquier número natural 𝑛 en 𝑁.
En este modelo extendido, los axiomas de Peano se siguen cumpliendo, y 𝑐 > 𝑘 para cualquier 𝑘 ≤ 𝑛. Por lo tanto, cada subconjunto finito Δ es satisfacible.
Paso 3: Aplicar el Teorema de Compacidad
Dado que cada subconjunto finito de Γ es satisfacible, por el Teorema de Compacidad, el conjunto completo Γ es satisfacible. Esto significa que existe un modelo 𝑀 tal que: 𝑀 ⊨ Γ
Paso 4: Propiedades del Modelo No Estándar
En el modelo 𝑀:
Los axiomas se cumplen.
Existe un elemento 𝑐 en 𝑀 tal que 𝑐 > 𝑛 para cualquier número natural 𝑛.
Este modelo 𝑀 no puede ser isomorfo al modelo estándar 𝑁, porque 𝑁 no contiene ningún elemento que sea mayor que todos los números naturales. Por lo tanto, 𝑀 es un modelo no estándar de la aritmética de primer orden.
