Ejemplo de conjunto no enumerable recursivamente $A \subseteq \mathbb{N}$

Question

Puede alguien darme un ejemplo si un conjunto no recursivamente enumerable $A \subseteq \mathbb{N}$ ?

Se me ocurrió esta pregunta, al tratar de demostrar, que existen funciones parciales $f: \mathbb{N} \rightsquigarrow \mathbb{N}$ que son constantes para algún valor (cuando se detienen), pero no recursivas:

Como sé que un conjunto es recursivamente enumerable si es el dominio de una función parcial recursiva, para encontrar un ejemplo de tal conjunto, tendría que demostrar que no importa qué función parcial cuyo dominio sea $A$ Yo tomaría, no sería recursivo. No he podido demostrar lo anterior, aunque intuitivamente me parece cierto. Pero como no pude demostrarlo y la existencia de tal contraejemplo es aún más fuerte (porque tendría que demostrar que toda una clase de esas funciones parciales no son recursivas) me hizo preguntarme si puede existir tal conjunto.

Answer 1

Otra forma de demostrar que tales conjuntos existen es mediante la diagonalización. Por ejemplo, tomemos el conjunto de todos los (códigos) de funciones recursivas totales.

Supongamos que existe una enumeración de la misma, es decir, que existe una máquina de Turing que enumera estas funciones (y digamos que esta enumeración es $(f_n)_{n\in\mathbb{N}}$ ). Ahora defina una función $g$ de la siguiente manera: $g(n)=f_n(n)+1$ . Obsérvese que esta función es recursiva y tiene como dominio los números naturales enteros, por tanto es una función recursiva total. Pero esto es imposible ya que difiere de toda función recursiva total en al menos un punto.

Answer 2

El complemento de cualquier conjunto recursivamente enumerable pero no recursivo servirá (si un conjunto e.r. tiene un complemento e.r. entonces es recursivo). Por ejemplo, el conjunto de números que no son los números de Gödel de un teorema de la Aritmética de Peano no es recursivamente enumerable. Lo mismo para el conjunto de números que codifican (bajo alguna codificación fija) un par $(T, x)$ de una máquina de Turing $T$ y una entrada $x$ de manera que la máquina $T$ hace pas se detiene cuando se le da la entrada $x$ .

Answer 3

Un buen ejemplo diferente a los mencionados hasta ahora es el siguiente:

Fijar una codificación (recursiva) de fórmulas por números, y dejar que $A$ sea el conjunto de códigos de sentencias $\phi$ que son verdaderos para los números naturales.

Este conjunto no puede ser r.e. por el teorema de incompletitud porque $A$ codifica una teoría consistente completa que extiende la Aritmética de Peano (es decir, la teoría de ${\mathbb N}$ ). Tenga en cuenta que en este ejemplo $A$ es un conjunto bastante complicado desde el punto de vista de la teoría de la computabilidad: Codifica recursivamente todos los conjuntos recursivos, todos los conjuntos de e.r., todos los conjuntos de e.r., etc.

De hecho, una construcción fácil muestra que hay tantos conjuntos $A$ codificar extensiones consistentes completas de PA como hay números reales: Enumerar todas las sentencias como $\phi_0,\phi_1,\dots$ Construye un árbol: En la parte inferior tenemos a PA. Dado un nodo en la profundidad $n$ y una teoría $T_n$ que se le adjunta, este nodo tiene como máximo dos sucesores inmediatos: extender a $T_n+\phi_n$ si esto es coherente, y a $T_n+\lnot\phi_n$ si esto es consistente. Si sólo uno de ellos es consistente, ésta es la única extensión. Si $T_n$ es consistente, al menos una de estas dos extensiones es consistente. Dado que $T_n$ es una extensión recursiva de PA (siendo PA y un número finito de "axiomas" adicionales), no es completa, por lo que finalmente tendremos dos extensiones. Esto demuestra que el árbol que obtenemos tiene $|2^{\mathbb N}|$ muchas ramas, cualquiera de las cuales codifica una extensión consistente completa de PA. Ninguna de estas extensiones es r.e. como antes.

Por supuesto, podemos producir muchos ejemplos a partir del hecho de que sólo hay un número contable de conjuntos r.e. pero un número incontable de subconjuntos de ${\mathbb N}$ . Muchos de estos ejemplos no podremos exponerlos de forma razonable. Para ilustrarlo, he aquí un ejemplo técnico que es más bien de naturaleza teórica de conjuntos:

Si $M$ es un modelo transitivo contable de la teoría de conjuntos suficiente, entonces, por supuesto, sólo hay contablemente muchos conjuntos de números naturales en $M$ y todos los conjuntos r.e. están en $M$ . Cualquier conjunto que no esté en $M$ es un ejemplo. Podemos ser más explícitos; digamos que cualquier $A$ que es Cohen genérico sobre $M$ es un ejemplo. Estos $A$ puede construirse explícitamente a partir de una enumeración de $M$ . Por supuesto, es una historia diferente cómo "explícita" $M$ puede ser. Pero realmente podemos hacer $A$ definible trabajando dentro de $L$ tomando como $M$ el menor modelo de, por ejemplo, ZF con sustitución restringida a $\Sigma_2$ fórmulas, y dejando que $A$ sea el menos genérico de Cohen sobre $M$ . Menos se refiere aquí a la ordenación habitual de $L$ .

El objetivo de este último ejemplo es que el $A$ que obtenemos no codifica mucha información en términos teóricos de computabilidad; por ejemplo, el problema de Halting sobre $A$ tiene el mismo grado que el problema de Halting.

Answer 4

Para añadir otro ejemplo, he aquí un conjunto para el que ni él ni su complemento son recursivamente enumerables: El conjunto de todas las máquinas de Turing que aceptan exactamente 3 palabras. Hay reducciones sencillas tanto del problema de Halting como de su complemento a este conjunto.

De hecho, la mayoría de los conjuntos no son recursivamente enumerables, ya que hay $\aleph$ conjuntos (de cadenas finitas sobre un alfabeto finito - "lenguajes") sino sólo $\aleph_0$ Máquinas de Turing (y cada conjunto de e.r. está definido de forma única por una máquina de Turing que lo reconoce).