6.5: Funciones y computabilidad

En Sección\(1.3\) hicimos el comentario extrapersonal de que la mayoría de las funciones no están definidas por reglas (por lo que nos referimos a instrucciones para computar la función). Consideramos que una regla es una instrucción (en algún idioma) de longitud finita. Las funciones que están definidas inequívocamente por una regla de longitud finita se denominan funciones computables o recursivas. Naturalmente existe una definición matemática complicada de funciones recursivas, pero vamos a prescindir de las formalidades y decir que una función es recursiva, o computable, si existe una instrucción (de longitud finita) para encontrar la imagen de cualquier elemento en el dominio. ¿Cuántas funciones computables hay?

Restringiremos nuestra investigación a funciones desde\(\mathbb{N}\) hasta\(\mathbb{N}\). Consideramos las funciones como gráficas de funciones. Es decir, cada subconjunto de\(P(\mathbb{N} \times \mathbb{N})\) que satisface la definición de una función es una función en\(\mathbb{N}^{\mathbb{N}}\). ¿Todas esas funciones son computables? Es obvio que\[2^{\aleph_{0}} \leq\left|\mathbb{N}^{\mathbb{N}}\right| \text {. }\] (¿Por qué?) De hecho se puede demostrar que los sets son biyectivos. Entonces hay incontables muchas funciones en\(\mathbb{N}^{\mathbb{N}}\). ¿Cuántas instrucciones para las funciones de cómputos hay? Una instrucción es una cadena finita, o secuencia, de símbolos. Por ejemplo, una instrucción para la función que cuadra números naturales es\[f(x)=x^{2} .\] Esta es una secuencia finita de siete símbolos. La instrucción da suficiente información para calcular la imagen de cualquier número natural. Hay muchas otras reglas para computar esta función. Por ejemplo, la regla\[f(x)=x \cdot x\] obviamente define la misma función, pero la instrucción es diferente, contiene un símbolo más. Considere el conjunto de todas las instrucciones posibles para las funciones de cómputos de números naturales. ¿Cómo se formulan las instrucciones? Se produce una secuencia finita de símbolos que forma una guía explícita para computar la imagen de cualquier número natural.

Dejar\(X\) ser el conjunto de todos los símbolos que aparecen en las instrucciones para computar funciones de números naturales. El conjunto\(X\) incluirá letras, dígitos, símbolos para operaciones, símbolos para relaciones y potencialmente cualquier otro símbolo que puedas ver en un libro sobre matemáticas. ¿Qué tan grande es\(X\)? Si requieres que cada símbolo aparezca en algún diccionario real, claramente sería finito. Probablemente desee permitir que aparezca cualquier número natural en la instrucción. Sin embargo, aunque hay infinitamente muchos números naturales, solo necesitamos diez símbolos para nombrarlos a todos. Parece que razonablemente podemos exigir que\(X\) sea finito, pero como resulta, podemos permitir que sea contablemente infinito sin cambiar nuestra conclusión.\(X\)

Si hay algún lenguaje con muchos símbolos contables en los que pueda escribirse el conjunto de todas las instrucciones para funciones de cómputos, entonces podemos suponer que\(X\) es contable. Si\(F\) es una instrucción o regla (y por lo tanto una secuencia finita de símbolos de\(X\)), entonces hay\(N \in \mathbb{N}\) tal que\[F \in X^{N} \text {. }\] Así se ve fácilmente que el conjunto de todas las instrucciones posibles para los elementos de\(\mathbb{N}^{\mathbb{N}}, I\), satisface \[I \preceq \bigcup_{N \in \mathbb{N}} X^{N} .\]Porque\(N \in \mathbb{N}, X^{N}\) es el producto directo de\(N\) factores de\(X\), y por Teorema\(6.20\),\[\left|X^{N}\right| \leq \aleph_{0} .\] El conjunto\(\bigcup_{N \in \mathbb{N}} X^{N}\) es la unión contable de conjuntos contables, y por Teorema \(6.16\)es contable. Por lo tanto, son incontables muchas funciones de los números naturales que no están definidas por reglas.

Para un tratamiento más exhaustivo de la teoría de conjuntos, consulte el libro [5] de Yiannis Moschovakis.