Conjuntos Recursivamente Enumerables en Teoría de la Recursión
Definición de Conjuntos Recursivamente Enumerables (r.e.)
Un conjunto \(A \subseteq \mathbb{N}\) es recursivamente enumerable (r.e.) si existe una máquina de Turing que lo enumera, es decir, una función computable parcial \(ϕ_e(x)\) tal que:
- Si \(x \in A\), entonces \(x\) aparece en la salida en algún tiempo finito.
- Si \(x \notin A\), la máquina puede no detenerse nunca.
En notación formal: $$\Large A = \{ x \mid \exists t, M(x,t) \text{ se detiene} \} $$
Propiedades de los Conjuntos r.e.
- Cerradura bajo la unión: Si \(A\) y \(B\) son r.e., entonces \(A \cup B\) también es r.e.
- Cerradura bajo intersección: Si \(A\) y \(B\) son r.e., entonces \(A \cap B\) también es r.e.
- Complementación no garantizada: El complemento de un conjunto r.e. no siempre es r.e. Si tanto \(A\) como \(\overline{A}\) son r.e., entonces \(A\) es recursivo.
Relación con Problemas de Decidibilidad
Un conjunto r.e. es decidible si y solo si existe una máquina de Turing que siempre termina para cualquier entrada, decidiendo si pertenece o no al conjunto. Esto significa que un conjunto es r.e. pero no recursivo si se puede enumerar, pero su complemento no lo es.
Clases de Complejidad Relacionadas
- \(\Sigma_1^0\)-completitud: Todo conjunto r.e. es de la forma \(\Sigma_1^0\) en la jerarquía aritmética.
- Reducciones de Turing: Un conjunto \(A\) es r.e. si existe una máquina de Turing que puede enumerarlo usando consultas a otro conjunto \(B\), es decir, \(A \leq_T B\).
Aplicaciones
- Problema de la parada: El conjunto de códigos de programas que terminan es r.e., pero no recursivo.
- Lenguajes formales: En la teoría de autómatas, los lenguajes r.e. son aquellos reconocidos por máquinas de Turing.
- Lógica Matemática: Se utilizan en teoría de la demostración y modelos computacionales.