Función computable para niños

Las funciones computables son un concepto fundamental en la teoría de la computabilidad. Son, en pocas palabras, las funciones que pueden ser calculadas por una máquina de Turing, que es un modelo teórico de computadora.

Estas funciones nos permiten hablar sobre qué se puede calcular y qué no, sin tener que mencionar un tipo específico de computadora. Aunque cualquier definición debe referirse a un modelo de cálculo, todas las definiciones válidas llegan a la misma clase de funciones.

Antes de que se definiera con precisión el término "función computable", los matemáticos usaban la expresión informal "efectivamente calculable". Hoy en día, estos dos términos se consideran lo mismo. Es importante saber que una función "efectivamente calculable" no significa que se pueda calcular "rápidamente". De hecho, algunas funciones computables tardarían muchísimo tiempo en calcularse, incluso más allá de lo que podemos imaginar. Los campos de la computabilidad práctica y la complejidad computacional estudian las funciones que sí pueden calcularse de forma eficiente.

Según la tesis de Church-Turing, las funciones computables son exactamente aquellas que se pueden calcular usando un dispositivo mecánico, siempre que se tenga tiempo y espacio de almacenamiento ilimitados. Esto significa que una función es computable si y solo si existe un algoritmo para ella. Un algoritmo, en este sentido, es una serie de pasos que una persona podría seguir con tiempo y papel ilimitados.

¿Qué son las funciones computables?

Las funciones computables son una manera formal de entender lo que es un algoritmo. De acuerdo con la tesis de Church-Turing, son exactamente las funciones que una máquina de Turing puede calcular. La idea de que una función sea computable puede adaptarse a diferentes conjuntos de números o a otras funciones, usando máquinas de Turing con "oráculos" (una especie de ayuda externa).

Estas funciones se usan para hablar de lo que se puede calcular sin mencionar un modelo de computadora específico, como una máquina de Turing o una máquina de registros.

La Tesis de Church-Turing también dice que las funciones computables son lo mismo que las funciones definidas por funciones recursivas, el cálculo lambda o los algoritmos de Markov.

También se pueden definir como los algoritmos que pueden ser calculados por una máquina de Turing, una máquina de Post o una máquina de registros.

En la Teoría de la complejidad computacional, el desafío de saber cuán compleja es una función computable se conoce como un problema de funciones.

¿Cómo se definen las funciones computables?

La computabilidad de una función es una idea que se puede describir de forma sencilla: una función es computable si su resultado se puede obtener siguiendo un procedimiento efectivo. De manera más formal, una función que toma números naturales y devuelve un número natural es computable si existe un procedimiento efectivo que, al darle cualquier grupo de números naturales, produce el valor de la función. En este artículo, asumimos que las funciones computables toman un número finito de números naturales como entrada y producen un solo número natural como salida.

Existen varias definiciones formales y matemáticas para las funciones computables. La clase de funciones computables se puede definir usando muchos modelos de computación que son equivalentes, como:

• Máquina de Turing
• Funciones μ-recursivas
• Cálculo lambda
• Máquinas Post (Máquinas Post-Turing y máquinas de etiquetas)
• Máquina de registro

Aunque estos modelos usan diferentes formas de representar las funciones, sus entradas y sus salidas, se pueden traducir entre sí. Esto significa que cada modelo describe esencialmente la misma clase de funciones, lo que sugiere que la computabilidad formal es una idea natural y no demasiado limitada. A veces, estas funciones se llaman "recursivas", para diferenciarlas del término informal "computables".

Por ejemplo, las funciones computables pueden formalizarse como funciones μ-recursivas, que son funciones que toman grupos finitos de números naturales y devuelven un solo número natural. Son el grupo más pequeño de funciones que incluye las funciones constantes, la función sucesora y la función de proyección, y se mantienen dentro de este grupo al usar la composición, la recurrencia primitiva y el operador μ.

De forma equivalente, las funciones computables pueden formalizarse como funciones que pueden ser calculadas por un agente de cálculo idealizado, como una máquina de Turing o una máquina de registro. Formalmente, una función parcial (una función que no está definida para todas las entradas posibles) puede ser calculada si existe un programa de computadora con estas características:

1. Si el valor de la función está definido para una entrada, el programa terminará con ese valor guardado en la memoria.
2. Si el valor de la función no está definido para una entrada, el programa nunca terminará.

Una función parcial se llama parcialmente computable si su gráfico (el conjunto de pares de entrada y salida) es un conjunto enumerable.

Una función total (definida para todas las entradas) se llama computable si su gráfico es un conjunto recursivo.

Una función computable que devuelve un valor verdadero o falso (0 o 1) se llama predicado computable.

Características de las funciones computables

La característica principal de una función computable es que debe existir un procedimiento finito (un algoritmo) que explique cómo calcularla. Los modelos de computación que mencionamos antes interpretan de diferentes maneras qué es un procedimiento y cómo se usa, pero todas estas interpretaciones comparten muchas propiedades. El hecho de que estos modelos den clases equivalentes de funciones computables se debe a que cada modelo puede "leer" e "imitar" un procedimiento de cualquiera de los otros modelos, de forma similar a como un compilador puede traducir instrucciones de un lenguaje de programación a otro.

Enderton (1977) describe las siguientes características de un procedimiento para calcular una función computable; otros, como Turing (1936) y Rogers (1967), han dado descripciones similares:

• "Debe haber instrucciones exactas (es decir, un programa), de longitud finita, para el procedimiento". Esto significa que toda función computable debe tener un programa finito que explique completamente cómo calcularla. Se puede calcular la función simplemente siguiendo las instrucciones; no se necesita adivinar ni tener conocimientos especiales.
• "Si al procedimiento se le da una entrada que está en el dominio de la función, entonces después de un número finito de pasos, el procedimiento debe terminar y producir el resultado". Esto significa que el procedimiento avanza paso a paso, con una regla específica para cada paso del cálculo. Solo se pueden realizar un número finito de pasos antes de que se obtenga el valor de la función.
• "Si al procedimiento se le da una entrada que no está en el dominio de la función, entonces el procedimiento podría seguir para siempre, sin detenerse nunca. O podría quedarse atascado en algún punto (es decir, una de sus instrucciones no puede ejecutarse), pero no debe intentar producir un valor para la función con esa entrada". Por lo tanto, si alguna vez se encuentra un valor para la función, debe ser el valor correcto. El sistema de cálculo no necesita distinguir entre resultados correctos e incorrectos, porque el procedimiento se define como correcto solo si produce un resultado.

Enderton también aclara estos tres requisitos:

1. El procedimiento debe funcionar teóricamente para entradas de cualquier tamaño. No se asume que las entradas sean pequeñas.
2. Se requiere que el procedimiento se detenga después de un número finito de pasos para dar una salida, pero puede tomar un número ilimitado de pasos antes de detenerse. No hay límite de tiempo.
3. Aunque el procedimiento puede usar solo una cantidad finita de espacio de almacenamiento durante un cálculo exitoso, no hay límite en la cantidad total de espacio que se puede usar. Se asume que se puede proporcionar espacio de almacenamiento adicional al procedimiento siempre que lo necesite.

En resumen, desde este punto de vista, una función es computable si:

• Dada una entrada de su dominio, y posiblemente con espacio de almacenamiento ilimitado, puede dar la salida correspondiente siguiendo un procedimiento (programa, algoritmo) que está formado por un número finito de instrucciones exactas y claras.
  • Luego, devuelve ese resultado (se detiene) en un número finito de pasos.
  • Si se le da una entrada que no está en su dominio, o bien nunca se detiene o se queda atascado.

El campo de la Teoría de la complejidad computacional estudia las funciones con límites específicos de tiempo y/o espacio permitidos para un cálculo exitoso.

Conjuntos y relaciones computables

Un conjunto de números naturales se llama computable (también conocido como recursivo o decidible) si existe una función computable y total que, para cualquier número natural, devuelve 1 si el número está en el conjunto y 0 si no lo está.

Un conjunto de números naturales se llama computablemente enumerable (también conocido como recursivamente enumerable o semidecidible) si existe una función computable tal que el valor de la función está definido si y solo si el número está en el conjunto. Así, un conjunto es computablemente enumerable si y solo si es el dominio de alguna función computable. La palabra "enumerable" se usa porque las siguientes afirmaciones son equivalentes para un subconjunto no vacío de los números naturales:

• El conjunto es el dominio de una función computable.
• El conjunto es el rango de una función total computable. Si el conjunto es infinito, se puede asumir que la función es inyectiva (cada entrada da una salida diferente).

Si un conjunto es el rango de una función, entonces la función puede verse como una enumeración del conjunto, porque la lista de resultados incluirá cada elemento del conjunto.

Dado que cada relación matemática sobre los números naturales puede identificarse con un conjunto correspondiente de secuencias finitas de números naturales, las ideas de relación computable y relación computablemente enumerable pueden definirse a partir de sus equivalentes para conjuntos.

Lenguajes formales

En la Teoría de la computabilidad en informática, es común estudiar los lenguajes formales. Un alfabeto es cualquier conjunto de símbolos. Una palabra en un alfabeto es una secuencia finita de símbolos de ese alfabeto; el mismo símbolo puede usarse varias veces. Por ejemplo, las cadenas binarias son palabras del alfabeto {0, 1}. Un lenguaje es un subconjunto de todas las palabras posibles de un alfabeto fijo. Por ejemplo, el conjunto de todas las cadenas binarias que contienen exactamente tres unos es un lenguaje sobre el alfabeto binario.

Una característica clave de un lenguaje formal es la dificultad para decidir si una palabra dada pertenece al lenguaje. Se debe desarrollar un sistema de codificación que permita a una función computable tomar una palabra arbitraria del lenguaje como entrada; esto suele ser algo rutinario. Un lenguaje se llama computable (también conocido como recursivo o decidible) si existe una función computable que, para cada palabra del alfabeto, devuelve 1 si la palabra está en el lenguaje y 0 si no lo está. Así, un lenguaje es computable solo si existe un procedimiento capaz de decir correctamente si cualquier palabra pertenece al lenguaje.

Un lenguaje es computablemente enumerable (también conocido como recursivamente enumerable o semidecidible) si existe una función computable tal que el valor de la función está definido si y solo si la palabra está en el lenguaje. El término "enumerable" tiene el mismo origen que en los conjuntos computablemente enumerables de números naturales.

Ejemplos de funciones computables

Las siguientes funciones son computables:

• Cualquier función con un dominio finito; por ejemplo, cualquier secuencia finita de números naturales.
• Cualquier función constante, donde el resultado es siempre el mismo número, sin importar la entrada.
• La Suma de dos números.
• El máximo común divisor de dos números.
• El coeficiente de Bézout de dos números.
• El factor primo más pequeño de un número.

Si f y g son funciones computables, entonces también lo son: f + g, f * g, la composición de f y g (si f es una operación con una sola entrada), el máximo de (f,g), el mínimo de (f,g), y muchas otras combinaciones.

Los siguientes ejemplos muestran que una función puede ser computable aunque no sepamos qué algoritmo la calcula:

• La función f que devuelve 1 si hay una secuencia de al menos n cincos consecutivos en la expansión decimal de π, y 0 en caso contrario, es computable. (La función f es la función constante 1, que es computable, o bien existe un número k tal que f(n) = 1 si n < k y f(n) = 0 si n ≥ k. Toda función de este tipo es computable. No se sabe si hay series arbitrariamente largas de cincos en la expansión decimal de π, así que no sabemos cuál de esas funciones es f. Sin embargo, sabemos que la función f debe ser computable).
• Cada segmento finito de una secuencia no computable de números naturales (como la Función del castor ocupado Σ) es computable. Por ejemplo, para cada número natural n, existe un algoritmo que calcula la secuencia finita Σ(0), Σ(1), Σ(2), ..., Σ(n) – a diferencia del hecho de que no hay algoritmo que calcule la secuencia Σ completa, es decir, Σ(n) para todos los n. Por lo tanto, "Imprimir 0, 1, 4, 6, 13" es un algoritmo sencillo para calcular Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); de manera similar, para cualquier valor dado de n, tal algoritmo sencillo existe (aunque nunca pueda ser conocido o producido por nadie) para calcular Σ(0), Σ(1), Σ(2), ..., Σ(n).

Propiedades de las funciones computables

• El conjunto de las funciones computables es numerable (se pueden listar).
• Si f y g son funciones computables, entonces f + g, f * g y f compuesta con g también son funciones computables.
• Las funciones computables se pueden definir usando operaciones aritméticas.
• Una función que devuelve un valor verdadero o falso es un predicado computable si y solo si el lenguaje de las entradas que dan "verdadero" es un lenguaje recursivo.

Véase también

En inglés: Computable function Facts for Kids