¿Hay algún conjunto contable que no sea computablemente enumerable?

Un conjunto es contable si tiene una biyección con los números naturales, y es computablemente enumerable (ce) si existe un algoritmo que enumera sus miembros.

Cualquier conjunto enumerable computable no finito debe ser contable ya que podemos construir una biyección a partir de la enumeración.

¿Hay algún ejemplo de conjuntos contables que no sean computablemente enumerables? Es decir, existe una biyección entre este conjunto y los números naturales, pero no existe un algoritmo que pueda calcular esta biyección.

computability semi-decidability Peter Olson
fuente

La terminología no establecida es computablemente enumerable . Mucha gente dirá que "contable" y "enumerable" son sinónimos. Edité la pregunta en consecuencia.

Andrej Bauer

@AndrejBauer, computable y recursivo son sinónimos, ¿verdad?

rus9384

@ rus9384 Sí. Con respecto al vocabulario, la claridad debe reinar, como Robert Irving Soare escribe en Turing-Post Relativized Computability and Interactive Computing (2011) : en 1995 la confusión se había vuelto intolerable. Escribí un artículo sobre Computabilidad y Recursión para el Toro. de Sym. Lógica (1996) sobre la historia y las razones científicas de por qué deberíamos usar "computable" y no "recursivo" para significar "calculable". "Recursivo" debería significar "inductivo" como lo era para Dedekind e Hilbert. Al principio, pocos estaban dispuestos a hacer ese cambio ...

David Tonhofer

Respuestas:

¿Hay ejemplos de conjuntos contables que no sean enumerables?

Si. Todos los subconjuntos de los números naturales son contables, pero no todos son enumerables. (Prueba: hay innumerables subconjuntos diferentes de pero solo muchas máquinas de Turing que podrían actuar como enumeradores.) Por lo tanto, cualquier subconjunto de que ya sepa que no es enumerable recursivamente es un ejemplo. como el conjunto de todos los números que codifican las máquinas de Turing que se detienen para cada entrada. $\mathbb{N}$ $\mathbb{N}$

David Richerby
fuente

@JorgePerez No y no .

David Richerby

Esto demuestra la existencia, pero no da un ejemplo ...

BlueRaja - Danny Pflughoeft

@ BlueRaja-DannyPflughoeft, dar un ejemplo es lo mismo que enumerar uno. "¿Puedes dar un ejemplo de algo de lo que no puedes dar un ejemplo? ¿No? Por lo tanto, no hay nada de lo que no puedas dar un ejemplo". Eso es constructivismo matemático en pocas palabras.

Comodín el

¿Sería la imagen de la función de castor ocupado tal conjunto? Como está aumentando estrictamente, trivialmente forma una biyección con , pero no hay una máquina de Turing que pueda enumerar .

Σ

$\Sigma$

Σ

$\Sigma$

N

$\mathbb{N}$

Σ

$\Sigma$

orlp

@Wildcard No, dar un ejemplo es lo mismo que definir uno, ¿no? Hay conjuntos que se pueden definir pero no se pueden enumerar mediante un algoritmo, como el conjunto de todas las máquinas de Turing que no se detienen.

Tanner Swett

Sí, cada lenguaje indecidible (no semidecidible) tiene esta propiedad.

Por ejemplo, considere que el conjunto . $L = \{(x,M) \mid M \text{ does not halt on input } x \}$

Supongamos que tenemos un algoritmo que puede enumerar los miembros de este conjunto. Si existiera dicho algoritmo, podríamos utilizarlo para resolver el problema de detención con las entradas , con el siguiente algoritmo: $x,M$

Alterne entre correr máquina para pasos en , y enumerando el º miembro de . $M$ $n$ $x$ $n$ $L$

$M$ detiene o no se detiene en . Si se detiene, finalmente encontraremos una donde llegaremos a un estado de detención. Si no se detiene, finalmente alcanzaremos en nuestra enumeración. $x$ $n$ $(M,x)$

Por lo tanto, tenemos una reducción, y podemos concluir que no existe tal enumeración.

Tenga en cuenta que tales enumeraciones pueden existir para problemas semi-decidibles. Por ejemplo, puede enumerar el conjunto de todos los pares de entrada de máquina de detención enumerando todas las trazas posibles de todas las ejecuciones de Turing Machine después de pasos, y filtrando las que no terminan en un estado de detención. $n$

jmite
fuente

¿No hay idiomas con una complejidad incontable?

rus9384

@ rus9384 No estoy seguro de lo que quieres decir. "Incontable" es una medida de tamaño; La "complejidad" es una medida de lo difícil que es decidir. Pero no hay innumerables idiomas de cadenas finitas: si desea que un idioma sea incontable, debe permitir cadenas infinitas (o un "alfabeto" incontable, o ambos).

David Richerby

@DavidRicherby, bueno, ¿jmite afirma que cada problema indecidible funciona con cadenas finitas? Creo que eso es válido solo para cada problema indecidible reconocible de Turing .

rus9384

@ rus9384 Cualquier idioma sobre un alfabeto finito es contable, y la computabilidad generalmente ignora los alfabetos infinitos. Ver también esta pregunta .

jmite

@ rus9384 sí, un idioma es un conjunto de cadenas finitas sobre un alfabeto finito. Cualquier cosa así es contable. Si desea obtener un lenguaje incontable, debe eliminar una o ambas instancias de "finito" de esa definición. Pero si alguien solo dice "idioma", significa un conjunto de cadenas finitas sobre un alfabeto finito.

David Richerby

En la teoría de la computabilidad tratamos con subconjuntos de , donde . Este lenguaje es infinitamente contable, por lo que cualquier subconjunto es contable. Además, hay muchos lenguajes indecidibles pero recursivamente enumerables cuyos complementos no son recursivamente enumerables. Estos lenguajes son subconjuntos de y, por lo tanto, son contables. $\Sigma^*$ $\Sigma = \{0,1\}$ $L \subseteq \Sigma^*$ $\Sigma^*$

fade2black
fuente

No necesariamente tratamos con cadenas binarias. Hay muchos casos en los que podríamos estar interesados en cadenas sobre otros alfabetos, y las personas que llaman a la computabilidad "teoría de la recursividad" tienden a tratar directamente con conjuntos de números naturales. (Es decir, los números en sí mismos se ven como primitivos, y no codificados como, por ejemplo, cadenas binarias.)

David Richerby

@DavidRicherby Hace un par de semanas me reclamó lo contrario en los comentarios a la respuesta de Yuvals. Y este no es el primer caso similar.

fade2black

Yuval publica muchas respuestas, y yo publico muchos comentarios, por lo que deberías ser más específico. Ciertamente mantengo mi comentario anterior, así que si dije lo contrario en algún momento, o estaba equivocado o confundido o me entendiste mal o estaba hablando de un escenario específico o algo así. Lo siento si te he confundido, ¡especialmente si lo hice diciendo algo poco claro o incorrecto!

David Richerby

@DavidRicherby, de hecho, cada alfabeto finito se puede reducir a binario, así que no entiendo cómo importa eso. ¿O tenemos un alfabeto infinitamente contable en este caso (donde cada número tiene un símbolo único)?

rus9384

{0, 1}

$\{0,1\}$