Función computable

Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por una máquina de Turing.

Las funciones computables se utilizan para hablar de computabilidad sin hacer referencia a ningún modelo de computación concreto, como las máquinas de Turing o las máquinas de registro. Cualquier definición, sin embargo, debe hacer referencia a algún modelo específico de computación, pero todas las definiciones válidas producen la misma clase de funciones. Los modelos particulares de computabilidad que dan lugar al conjunto de funciones computables son las funciones computables de Turings y las funciones recursivas generales.

Antes de la definición precisa de función computable, los matemáticos utilizaban a menudo el término informal efectivamente calculable. Desde entonces, este término se identifica con las funciones computables. Nótese que la computabilidad efectiva de estas funciones no implica que puedan ser eficientemente calculadas (es decir, calculadas en un tiempo razonable). De hecho, para algunas funciones efectivamente calculables se puede demostrar que cualquier algoritmo que las compute será muy ineficiente en el sentido de que el tiempo de ejecución del algoritmo aumenta exponencialmente (o incluso superexponencialmente) con la longitud de la entrada. Los campos de computabilidad factible y complejidad computacional estudian funciones que pueden ser computadas eficientemente.

Según la tesis de Church-Turing, las funciones computables son exactamente las funciones que pueden calcularse utilizando un dispositivo de cálculo mecánico dadas cantidades ilimitadas de tiempo y espacio de almacenamiento. Equivalentemente, esta tesis afirma que una función es computable si y sólo si tiene un algoritmo. Nótese que un algoritmo en este sentido se entiende como una secuencia de pasos que una persona con tiempo ilimitado y un suministro ilimitado de lápiz y papel podría seguir.

Los axiomas de Blum pueden utilizarse para definir una teoría de la complejidad computacional abstracta sobre el conjunto de funciones computables. En la teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable se conoce como problema de función.

Introducción[editar]

Las funciones computables son una formalización de la noción intuitiva de algoritmo y, según la tesis de Church-Turing, son exactamente las funciones que pueden ser calculadas con una máquina de Turing. La noción de la computabilidad de una función puede ser relativizada a un conjunto arbitrario de números naturales A, o equivalentemente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas con un oráculo por A o f. Tales funciones pueden ser llamadas A-computable o f-computable respectivamente. Antes de la definición precisa de una función computable los matemáticos usaban el término informal efectivamente computable.

Las funciones computables son usadas para discutir sobre computabilidad sin referirse a ningún modelo de computación concreto, como el de la máquina de Turing o el de la máquina de registros. Los axiomas de Blum pueden ser usados para definir una teoría de complejidad computacional abstracta sobre el conjunto de funciones computables.

Según la Tesis de Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidas por funciones recursivas, cálculo lambda, o algoritmos de Markov [1].

Alternativamente 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 teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable es conocido como un problema de funciones.

Definición[editar]

La computabilidad de una función es una noción informal. Una forma de describirla es decir que una función es computable si su valor puede obtenerse mediante un procedimiento efectivo. Con más rigor, una función $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ es computable si y sólo si existe un procedimiento efectivo que, dada cualquier $k$ -tupla $\mathbf {x}$ de números naturales, producirá el valor $f(\mathbf {x} )$ .^[1] De acuerdo con esta definición, el resto de este artículo supone que las funciones computables toman finitamente muchos números naturales como argumentos y producen un valor que es un único número natural.

Como contrapartida a esta descripción informal, existen múltiples definiciones formales y matemáticas. La clase de funciones computables se puede definir en muchos modelos de computación equivalentes, incluyendo

Máquina de Turing
μ-función recursiva
Cálculo lambda
Máquinas Post (Máquina Post-Turings y máquinas de etiquetas).
Máquina de registro

Aunque estos modelos utilizan diferentes representaciones para las funciones, sus entradas y sus salidas, existen traducciones entre dos modelos cualesquiera, por lo que cada modelo describe esencialmente la misma clase de funciones, dando lugar a la opinión de que la computabilidad formal es a la vez natural y no demasiado estrecha.^[2] Estas funciones se denominan a veces "recursivas", en contraste con el término informal "computables",^[3] una distinción derivada de una discusión de 1934 entre Kleene y Gödel.^[4]^p.6

Por ejemplo, se pueden formalizar funciones computables como funciónes μ-recursivas, que son funciones parciales que toman tuplas finitas de números naturales y devuelven un único número natural. Son la clase más pequeña de funciones parciales que incluye las funciones constante, sucesora y de proyección, y es cerrada bajo composición, recurrencia primitiva y el operador μ.

Equivalentemente, las funciones computables pueden formalizarse como funciones que pueden ser calculadas por un agente computacional idealizado como una máquina de Turing o una máquina de registro. Formalmente hablando, una función parcial $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ puede ser calculada si y sólo si existe un programa de ordenador con las siguientes propiedades:

Si $f(\mathbf {x} )$ está definido, entonces el programa terminará en la entrada $\mathbf {x}$ con el valor $f(\mathbf {x} )$ almacenado en la memoria del ordenador.
Si $f(\mathbf {x} )$ es indefinido, entonces el programa nunca termina en la entrada $\mathbf {x}$ .

Una función parcial

f:\subseteq \mathbb {N} \to \mathbb {N}

se llama parcialmente computable si el gráfico $f$ es un conjumerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito $\mathbf {P} ^{(1)}$ o ath> si el número de parámetros puede deducirse del contexto.

Una función total

f:\mathbb {N} \to \mathbb {N}

se llama computable si el gráfico de $f$ es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro normalmente se escribe $\mathbf {R} ^{(1)}$ o $\mathbf {R}$ .

Una función computable $f$ se llama predicado computable si es una función con valor booleano, es decir:

f:\subseteq \mathbb {N} \to \{0,1\}

Características de las funciones computables[editar]

Artículo principal: Algoritmo

La característica básica de una función computable es que debe existir un procedimiento finito (un algoritmo) que diga cómo calcular la función. Los modelos de computación enumerados anteriormente dan diferentes interpretaciones de lo que es un procedimiento y cómo se utiliza, pero estas interpretaciones comparten muchas propiedades. El hecho de que estos modelos den clases equivalentes de funciones computables proviene del hecho de que cada modelo es capaz de leer e imitar un procedimiento para cualquiera de los otros modelos, del mismo modo que un compilador es capaz de leer instrucciones en un lenguaje informático y emitir instrucciones en otro lenguaje.

Enderton [1977] da las siguientes características de un procedimiento para computar una función computable; caracterizaciones similares han sido dadas por Turing [1936], Rogers [1967], y otros.

"Debe haber instrucciones exactas (es decir, un programa), de longitud finita, para el procedimiento". Así pues, toda función computable debe tener un programa finito que describa completamente cómo debe calcularse la función. Es posible calcular la función simplemente siguiendo las instrucciones; no es necesario adivinar nada ni tener conocimientos especiales.
Si al procedimiento se le da una k -tupla x en el dominio de f, entonces después de un número finito de pasos discretos el procedimiento debe terminar y producir f(x)". Intuitivamente, el procedimiento procede paso a paso, con una regla específica para cubrir qué hacer en cada paso del cálculo. Sólo pueden realizarse un número finito de pasos antes de que se devuelva el valor de la función.
Si al procedimiento se le da una k -tupla x que no está en el dominio de f, entonces el procedimiento podría continuar para siempre, sin detenerse nunca. O podría atascarse en algún punto (es decir, una de sus instrucciones no puede ejecutarse), pero no debe pretender producir un valor para f en x". Por tanto, si alguna vez se encuentra un valor para f(x), debe ser el valor correcto. No es necesario que el agente informático distinga los resultados correctos de los incorrectos porque el procedimiento se define como correcto si y sólo si produce un resultado.

Enderton pasa a enumerar varias aclaraciones de estos 3 requisitos del procedimiento para una función computable:

El procedimiento debe funcionar teóricamente para argumentos arbitrariamente grandes. No se asume que los argumentos sean menores que el número de átomos de la Tierra, por ejemplo.
Se requiere que el procedimiento se detenga después de un número finito de pasos para producir una salida, pero puede tomar un número arbitrario de pasos antes de detenerse. No se asume ninguna limitación de tiempo.
Aunque el procedimiento puede utilizar sólo una cantidad finita de espacio de almacenamiento durante un cálculo con éxito, no hay límite en la cantidad de espacio que se utiliza. Se supone que se puede proporcionar espacio de almacenamiento adicional al procedimiento siempre que éste lo solicite.

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

dada una entrada de su dominio, posiblemente contando con un 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 no ambiguas;
- Entonces devuelve dicho resultado (se detiene) en un número finito de pasos; y
- 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 complejidad computacional estudia funciones con límites prescritos en el tiempo y/o espacio permitidos en una computación exitosa.

Conjuntos y relaciones computables[editar]

Un conjunto $A$ de números naturales se llama computable (sinónimos: recursivo, decidible) si existe una función computable, total $f$ } tal que para cualquier número natural $n$ , $f (n) = 1$ si $n$ está en $A$ y $f (n) = 0$ si $n$ no está en $A$ .

Un conjunto de números naturales se llama computablemente enumerable (sinónimos: recursivamente enumerable', semidecidible) si existe una función computable $f$ } tal que para cada número $n$ , $f (n)$ está definida si y sólo si. $n$ está en el conjunto. Así, un conjunto es computablemente enumerable si y sólo si es el dominio de alguna función computable. La palabra enumerable se utiliza porque los siguientes son equivalentes para un subconjunto no vacío $B$ de los números naturales:

$B$ es el dominio de una función computable.
$B$ es el rango de una función total computable. Si $B$ es infinito entonces se puede suponer que la función es inyectiva.

Si un conjunto $B$ es el rango de una función $f$ entonces la función puede verse como una enumeración de $B$ , porque la lista $f (0), f (1), ...$ incluirá cada elemento de $B$ .

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 nociones de relación computable y relación computablemente enumerable pueden definirse a partir de sus análogas para conjuntos.

Lenguajes formales[editar]

Artículo principal: Lenguaje formal

En Teoría de la computabilidad en informática, es común considerar lenguajes formales. Un alfabeto es un conjunto arbitrario. Una palabra en un alfabeto es una secuencia finita de símbolos del alfabeto; el mismo símbolo puede usarse más de una vez. Por ejemplo, las cadenas binarias son exactamente las palabras del alfabeto $Plantilla:0, 1 .$ . Un lenguaje es un subconjunto de la colección de todas las palabras de un alfabeto fijo. Por ejemplo, la colección de todas las cadenas binarias que contienen exactamente 3 unos es un lenguaje sobre el alfabeto binario.

Una propiedad clave de un lenguaje formal es el nivel de dificultad necesario para decidir si una palabra dada está en el lenguaje. Debe desarrollarse algún sistema de codificación que permita a una función computable tomar como entrada una palabra arbitraria del lenguaje; esto suele considerarse rutina. Un lenguaje se llama computable (sinónimos: recursivo, decidible) si existe una función computable $f$ tal que para cada palabra $w$ sobre el alfabeto, $f (w) = 1$ si la palabra está en la lengua y $f (w) = 0$ si la palabra no está en el lenguaje. Así, un lenguaje es computable sólo en el caso de que exista un procedimiento capaz de decir correctamente si palabras arbitrarias están en el lenguaje.

Un lenguaje es computablemente enumerable (sinónimos: recursivamente enumerable, semidecidible) si existe una función computable $f$ tal que $f (w)$ está definida si y sólo si la palabra $w$ está en el lenguaje. El término enumerable tiene la misma etimología que en conjuntos computablemente enumerables de números naturales.

Comentarios[editar]

A veces, por razones de claridad, se escribe una función computable como

g:\subseteq \mathbb {N} ^{k}\to \mathbb {N}

Se puede fácilmente codificar g en una nueva función

f:\subseteq \mathbb {N} \to \mathbb {N}

usando una función de pares.

Ejemplos[editar]

Las siguientes funciones son computables:

Cada función con un dominio finito; por ejemplo, cualquier secuencia finita de números naturales.
Cada función constante f : N^k → N', f(n₁,...n_k) := n.
Suma f : N² → N', f(n₁,n₂) := n₁ + n₂.
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 computables, entonces también lo son: f + g, f * g, $\color {Blue}f\circ g$ si f es unaria, max(f,g), min(f,g), $arg max {y \leq f (x)}$ y muchas más combinaciones.

Los siguientes ejemplos ilustran que una función puede ser computable aunque no se sepa qué algoritmo la computa.

La función f tal que f(n) = 1 si hay una secuencia de al menos n cincos consecutivos en la expansión decimal de π, y f(n) = 0 en caso contrario, es computable. (La función f es la función constante 1, que es computable, o bien existe un 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) - en contraste con el hecho de que no hay algoritmo que calcula la entera secuencia Σ, es decir, Σ(n) para todos los n. Por lo tanto, "Imprimir 0, 1, 4, 6, 13" es un algoritmo trivial para calcular Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); Del mismo modo, para cualquier valor dado de n, tal algoritmo trivial existe (aunque nunca pueda ser conocido o producido por nadie) para calcular Σ(0), Σ(1), Σ(2), . .., Σ(n).
Función constante f : N^k→ N, f(n₁,...n_k) := n

Adición f : N²→ N, f(n₁,n₂) := n₁ + n₂

Propiedades[editar]

El conjunto de las funciones computables es numerable.

Si $f$ y $g$ son funciones computables entonces $f+g$ , $f\cdot g$ y $f\circ g$ son funciones computables.

Las funciones computables son definibles aritméticamente.

Una función con valor booleano $f$ es un predicado computable si y sólo si el lenguaje $\{x\in \Sigma ^{*}:f(x)=1\}$ es recursivo.

Referencias[editar]

↑ Enderton, Herbert (2002). A Mathematical Introduction to Logic. USA: Elsevier. p. 209. ISBN 0-12-238452-0.
↑ Enderton, Herbert (2002). Una introducción matemática a la lógica (Second edición). USA: Elsevier. p. 208,262. ISBN 0-12-238452-0.
↑ C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundation of Mathematics, 2000), p. 4
↑ R. Soare, Computabilidad y recursión (1995). Consultado el 9 de noviembre de 2022.

Datos: Q1148456

[1] Enderton, Herbert (2002). A Mathematical Introduction to Logic. USA: Elsevier. p. 209. ISBN 0-12-238452-0.

[2] Enderton, Herbert (2002). Una introducción matemática a la lógica (Second edición). USA: Elsevier. p. 208,262. ISBN 0-12-238452-0.

[3] C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundation of Mathematics, 2000), p. 4

[4] R. Soare, Computabilidad y recursión (1995). Consultado el 9 de noviembre de 2022.

[1]

[2]

[3]

[4]