Establezca que ha establecido$S$ y puede probar que cualquier función de inyección que asigne$S$ a los números naturales no puede ser una función computable. ¿Puede$S$ seguir siendo contable? Y si es así, ¿alguien sabe de un ejemplo de un conjunto contable sin función de conteo computable?
Respuesta
¿Demasiados anuncios?
Por una "función de conteo" asumo que te refieres a una función biyectiva computable del conjunto a los números naturales.
Si un conjunto tiene tal función de conteo, y esa función de cómputo es computable, entonces el propio conjunto es computableblemente enumerable, mediante técnicas estándar.
Por lo tanto, cualquier conjunto de números naturales que no sean de CE será un ejemplo de un conjunto contable que no tiene función de conteo computable.
