Lenguajes Formales y Computabilidad

Edición 2024

Repositorio que contiene todo el material correspondiente a la materia de Lenguajes Formales y Computabilidad de 4to año de la Licenciatura en Ciencias de la Computación de FAMAF.

Equipo Docente

• Teóricos: Diego Vaggione
• Prácticos: Martín Vilela y Mariana Badano

Material de Estudio

Guías y Resúmenes

Unidad	Tema	Material	Resumen
1	Notación + Conceptos básicos + Funciones/Conjuntos $\Sigma$-mixtos + Notación $\lambda$	Guía 1	MD y PDF
2	Infinituplas + Órdenes totales + Orden natural sobre $\Sigma^*$	Guía 2	MD y PDF
3	Procedimientos efectivos + Funciones/Conjuntos $\Sigma$-efectivamente computables + Conjuntos $\Sigma$-efectivamente enumerables	Guía 3	MD y PDF
4	Paradigma de Turing (Máquina de Turing + Funciones $\Sigma$-Turing computables)	Guía 4	MD y PDF
5	Paradigma de Godel (Funciones/Conjuntos $\Sigma$-recursiva y recursivas primitivas)	Guía 5	MD y PDF
6	Sumatoria, productoria, concatenatoria, cuantificación acotada de predicados y minimización de funciones $\Sigma$-recursivas + Conjuntos $\Sigma$-recursivamente enumerables + Independencia del alfabeto	Guía 6	MD y PDF
7	Paradigma imperativo de Neumann: El lenguaje $S^{\Sigma}$ (Funciones/Conjuntos $\Sigma$-computables + Conjuntos $\Sigma$-enumerables + Macros)	Guía 7	MD y PDF
8	Comparación entre paradigmas + Tesis de Church	Guía 8	MD y PDF
9	Resultados básicos de computabilidad	Guía 9	MD y PDF

Lista de Combos (Examen Final - Parte Teórica)

Definiciones y convenciones notacionales

Combo	Tema	Material
1	Conjunto $\Sigma$-r, $\langle s_1,s_2,..\rangle$, función $\Sigma$-mixta, "familia $\Sigma$-indexada de funciones", $R(f,\mathcal{G})$	LyX y PDF
2	$d\overset{n}{\vdash}d'$, $L(M)$, $H(M)$, "función de tipo $(n,m,s)$ ", $(x)$, $(x)_i$	LyX y PDF
3	Conjunto $\Sigma$-r.e., $s^\leq$, $*^\leq$, $\#^\leq$	LyX y PDF
4	Función $\Sigma$-efectivamente computable y procedimiento efectivo que la computa	LyX y PDF
5	Conjunto $\Sigma$-efectivamente computable y procedimiento efectivo que decide la pertenencia	LyX y PDF
6	Conjunto $\Sigma$-efectivamente enumerable y procedimiento efectivo que lo enumera	LyX y PDF
7	Función $\Sigma$-Turing computable y máquina que la computa	LyX y PDF
8	$M(P)$, $Lt$, conjunto rectangular, conjunto de tipo $(n,m)$	LyX y PDF
9	" $I$ es instrucción de $S^\Sigma$ ", $\mathcal{P}$ es programa de $S^\Sigma$, $I_i^\mathcal{P}$, $n(\mathcal{P})$, $Bas$	LyX y PDF
10	(Relativo a $S^\Sigma$) "Estado", "descripción instantánea", $S_\mathcal{P}$, "estado obtenido luego de $t$ pasos", " $\mathcal{P}$ se detiene luego de $t$ pasos"	LyX y PDF
11	$\Psi_\mathcal{P}^{n,m,\#}$, función $\Sigma$-computable y programa que la computa, $M^\leq(P)$	LyX y PDF
12	Conjunto $\Sigma$-computable, conjunto $\Sigma$-enumerable y programa que lo enumera	LyX y PDF
13	$i^{n,m}$, $E_{\#}^{n,m}$, $E_*^{n,m}$, $E_{\#j}^{n,m}$, $E_{*j}^{n,m}$, $Halt^{n,m}$, $T^{n,m}$, $AutoHalt^\Sigma$ y los conjuntos $A$ y $N$	LyX y PDF
14	Notación lambda	LyX y PDF
15	Macro de asignación	LyX y PDF
16	Macro IF	LyX y PDF

Teoremas

Combo	Tema	Material
1	Caracterización de conjuntos p.r., Neumann vence a Godel	LyX y PDF
2	Lema de división por casos para funciones p.r., Caracterización básica de conjuntos enumerables	LyX y PDF
3	Godel vence a Neumann, Caracterización de conjuntos efectivamente computables	LyX y PDF
4	Caracterización básica de conjuntos enumerables, Lema de la sumatoria	LyX y PDF
5	Lema de intersección de conjuntos $\Sigma$-efectivamente enumerables, Lema de cuantificación acotada	LyX y PDF
6	Efectivamente computable implica efectivamente enumerable, Caracterización de conjuntos r.e.	LyX y PDF
7	Lema de minimización acotada, función con clausura	LyX y PDF
8	$AutoHalt^\Sigma$ no $\Sigma$-r., $AutoHalt^\Sigma$ no $\Sigma$-efectivamente computable, $A$ $\Sigma$-r.e. y no $\Sigma$-r. y $N$ no $\Sigma$-r.e., Neumann vence a Godel	LyX y PDF
9	Lema de división por casos para funciones recursivas, $Halt^{n,m}$ es $(\Sigma\cup\Sigma_p)$-p.r., $T^{n,m}$ es $(\Sigma\cup\Sigma_p)$-r.	LyX y PDF