Por un lado, que el teorema en su libro se refiere sólo a los conjuntos de números naturales, que es el contexto de la introductorio de la teoría de la computabilidad. La computabilidad no se preocupa por la arbitraria de conjuntos, sino sólo aquellos cuyos elementos pueden ser pasados a una máquina de Turing. El básico, que es lo que la introducción de los libros se centran en, es cuando estamos mirando a la computabilidad de los conjuntos de productos naturales. Así que no se puede leer "conjunto" en el que el resultado a que se refieren arbitraria de conjuntos, que no es la intención.
El ejemplo de los números reales que no se sostienen. Como un ejemplo, el intervalo de $[0,2)$ fue reclamado para ser decidable. Imagínese que usted se vea más grande y más grande segmentos inicial de un único número: $1.9$, $1.99$, $1.9999$, etc. Tienes que finalmente decir si este número es en $[1,2)$. Por supuesto, esto es imposible para un algoritmo: el número podría ser igual a $2$, o que podría llegar a menos de $2$, y no hay manera de saber cual de estos ocurre en una cantidad finita de tiempo. Podemos mostrar que, en realidad, la única decidable conjuntos de números reales son los de toda la recta real y el conjunto vacío.
Sin embargo, si nos trasladamos a un espacio diferente, entonces la respuesta será "sí". El trabajo con el espacio de todas las secuencias infinitas de $0$s y $1$s. Deje $S$ el conjunto de secuencias cuyo primer elemento es una $0$. Este es un decidable conjunto, debido a que el algoritmo sólo tiene que mirar en el primer elemento para decidir si una secuencia infinita está en el conjunto. El complemento de a es el conjunto de todas las infinitas secuencias binarias que comienzan con $1$. Que es una multitud innumerable, por lo que no puede ser enumerado en el sentido de que tiene en mente. Tampoco puede el conjunto de todas las secuencias que comienzan con $0$, por lo que el decidable conjunto en sí no es enumerable, en el sentido de que tiene en mente.
Hay un problema más profundo, sin embargo. Cuando nos fijamos en los subconjuntos de los números naturales, los siguientes son equivalentes las propiedades de un conjunto $S$:
- El conjunto $S$ es enumerable
- El conjunto $S$ es el rango de un total computable de la función
- El conjunto $S$ es el dominio de un total computable de la función
Cuando comenzamos a mirar a la computabilidad en otros, infinidad de conjuntos, a menudo usamos la tercera viñeta como la definición de "enumerable", en lugar de la segunda. Con el cambio de definición, se convierte en la verdadera nuevo que cada decidable conjunto es enumerable.
