Función computable

Las funciones computables son el objeto de estudio fundamental en la teoría de la computabilidad . De manera informal, una función es computable si existe un algoritmo que calcula su valor para cada valor de su argumento. Debido a la falta de una definición precisa del concepto de algoritmo, toda definición formal de computabilidad debe referirse a un modelo de computación específico .

Se han propuesto numerosos modelos de computación, entre los que destacan las máquinas de Turing , las máquinas de registros , el cálculo lambda y las funciones recursivas generales . Si bien estos cuatro modelos son de naturaleza muy diferente, proporcionan exactamente la misma clase de funciones computables y, para cada modelo de computación propuesto, las funciones computables para dicho modelo son computables para los cuatro modelos mencionados.

La tesis de Church-Turing es la afirmación indemostrable de que toda noción de computabilidad imaginable solo puede computar funciones que sean computables en el sentido antes mencionado.

Antes de la definición precisa de funciones computables, los matemáticos solían usar el término informal «efectivamente calculable» . Este término se ha asociado posteriormente con las funciones computables. La computabilidad efectiva de estas funciones no implica que puedan calcularse eficientemente (es decir, en un tiempo razonable). De hecho, para algunas funciones efectivamente calculables, se puede demostrar que cualquier algoritmo que las calcule será muy ineficiente, ya que su tiempo de ejecución aumenta exponencialmente (o incluso superexponencialmente ) con la longitud de la entrada. Los campos de la computabilidad factible y la complejidad computacional estudian las funciones que pueden calcularse eficientemente.

Los axiomas de Blum pueden utilizarse para definir una teoría abstracta de la complejidad computacional sobre el conjunto de funciones computables. En la teoría de la complejidad computacional, el problema de calcular el valor de una función se conoce como problema de función , a diferencia de los problemas de decisión, cuyos resultados son simplemente "sí" o "no".

Definición

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 mayor rigor, una función $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ es computable si existe un procedimiento efectivo que, dado 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 presupone que las funciones computables toman un número finito de números naturales como argumentos y producen un valor que es un único número natural.

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

Máquinas de Turing
funciones recursivas generales
Cálculo lambda
Máquinas post ( máquinas post-Turing y máquinas de etiquetas ).
Máquinas de caja registradora

Aunque estos modelos utilizan diferentes representaciones para las funciones, sus entradas y sus salidas, existen traducciones entre cualesquiera dos modelos, por lo que cada modelo describe esencialmente la misma clase de funciones, lo que da lugar a la opinión de que la computabilidad formal es natural y no demasiado restrictiva. ^{[ 2 ]} A estas funciones a veces se las denomina "recursivas", en contraste con el término informal "computable", ^{[ 3 ]} una distinción que surge de una discusión de 1934 entre Kleene y Gödel . ^{[ 4 ]}^{: 6}

Por ejemplo, se pueden formalizar las funciones computables como funciones μ-recursivas , que son funciones parciales que toman tuplas finitas de números naturales y devuelven un único número natural (como se indicó anteriormente). 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 , recursión primitiva y el operador μ .

De forma equivalente, 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 registros . Formalmente hablando, una función parcial $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ se puede calcular si existe un programa informático con las siguientes propiedades:

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

Características de las funciones computables

La característica básica de una función computable es que debe existir un procedimiento finito (un algoritmo ) que indique cómo calcularla. Los modelos de computación mencionados anteriormente ofrecen diferentes interpretaciones de qué es un procedimiento y cómo se utiliza, pero estas interpretaciones comparten muchas propiedades. El hecho de que estos modelos den lugar a clases equivalentes de funciones computables se debe a que cada modelo es capaz de leer e imitar un procedimiento de cualquiera de los otros modelos, de forma similar a como un compilador puede leer instrucciones en un lenguaje de programación y generar instrucciones en otro.

Enderton [1977] da las siguientes características de un procedimiento para calcular 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. Por lo tanto, toda función computable debe tener un programa finito que describa completamente cómo se debe calcular. Es posible calcular la función simplemente siguiendo las instrucciones; no se requiere adivinar ni tener conocimientos especiales.
Si se le proporciona al procedimiento una k -tupla x en el dominio de f , entonces, tras un número finito de pasos discretos, el procedimiento debe finalizar y producir f ( x ). Intuitivamente, el procedimiento avanza paso a paso, con una regla específica que define qué hacer en cada paso del cálculo. Solo se puede realizar un número finito de pasos antes de que se devuelva el valor de la función.
Si al procedimiento se le proporciona una k -tupla x que no pertenece al dominio de f , entonces el procedimiento podría continuar indefinidamente, sin detenerse jamás. O podría quedarse atascado en algún punto (es decir, una de sus instrucciones no podría ejecutarse), pero no debe pretender producir un valor para f en x . Por lo tanto, si alguna vez se encuentra un valor para f ( x ), debe ser el valor correcto. No es necesario que el agente computacional distinga entre resultados correctos e incorrectos, ya que el procedimiento se define como correcto si y solo si produce un resultado.

Enderton continúa enumerando varias aclaraciones de estos 3 requisitos del procedimiento para una función computable:

En teoría, el procedimiento debería funcionar para argumentos arbitrariamente grandes. No se presupone, por ejemplo, que los argumentos sean menores que el número de átomos en la Tierra.
El procedimiento debe detenerse tras un número finito de pasos para generar un resultado, pero puede tardar un número arbitrario de pasos antes de detenerse. No se asume ninguna limitación de tiempo.
Si bien el procedimiento puede utilizar una cantidad finita de espacio de almacenamiento durante un cálculo exitoso, no existe un límite en la cantidad de espacio que se utiliza. Se supone que se puede proporcionar espacio de almacenamiento adicional al procedimiento cuando este lo solicite.

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

Dado un dato de entrada de su dominio, posiblemente dependiendo de 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 e inequívocas;
devuelve dicha salida (se detiene) en un número finito de pasos; y
Si recibe una entrada que no está dentro de su dominio, o bien nunca se detiene o se bloquea.

El campo de la complejidad computacional estudia funciones con límites preestablecidos en el tiempo y/o el espacio permitidos para un cálculo exitoso.

Conjuntos computables y relaciones

Un conjunto $A$ de números naturales se denomina computable (sinónimos: recursivo , decidible ) si existe una función total computable $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 denomina enumerable computable (sinónimos: enumerable recursivamente , semidecidible ) si existe una función computable $f$ tal que, para cada número $n$ , $f (n)$ está definida si y solo si $n$ pertenece al conjunto. Por lo tanto, un conjunto es enumerable computable si y solo si es el dominio de alguna función computable. El término enumerable se utiliza porque las siguientes expresiones 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 computable total. 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 finita 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 enumerable computable pueden definirse a partir de sus análogos para conjuntos.

Lenguajes formales

En la teoría de la computabilidad en informática , es común considerar los lenguajes formales . Un alfabeto es un conjunto arbitrario. Una palabra en un alfabeto es una secuencia finita de símbolos del alfabeto; un mismo símbolo puede usarse más de una vez. Por ejemplo, las cadenas binarias son exactamente las palabras del alfabeto ${0, 1$ }. Un lenguaje es un subconjunto del conjunto de todas las palabras de un alfabeto fijo. Por ejemplo, el conjunto 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 requerido para determinar si una palabra dada pertenece a dicho lenguaje. Es necesario desarrollar un sistema de codificación que permita que una función computable tome como entrada una palabra arbitraria del lenguaje; esto generalmente se considera rutinario. Un lenguaje se denomina computable (sinónimos: recursivo , decidible ) si existe una función computable $f$ tal que, para cada palabra $w$ del alfabeto, $f (w) = 1$ si la palabra pertenece al lenguaje y $f (w) = 0$ si no pertenece. Por lo tanto, un lenguaje es computable si existe un procedimiento capaz de determinar correctamente si palabras arbitrarias pertenecen a él.

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

Ejemplos

Las siguientes funciones son computables:

Cada función tiene 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
Un 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 se desconozca qué algoritmo la calcula.

La función f tal que f ( n ) = 1 si existe 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 o bien 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. Se desconoce si existen secuencias arbitrariamente largas de cincos en la expansión decimal de π, por lo 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 Busy Beaver Σ) 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 existe ningún algoritmo que calcule la secuencia Σ completa , es decir, Σ( n ) para todo n . Así, "Imprimir 0, 1, 4, 6, 13" es un algoritmo trivial para calcular Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); de manera similar, para cualquier valor dado de n , existe un algoritmo trivial (aunque puede que nunca sea conocido o producido por nadie) para calcular Σ(0), Σ(1), Σ(2), ..., Σ( n ).

Tesis de Church-Turing

La tesis de Church-Turing afirma que cualquier función computable a partir de un procedimiento que posea las tres propiedades mencionadas anteriormente es una función computable. Dado que estas tres propiedades no se enuncian formalmente, la tesis de Church-Turing no puede demostrarse. Los siguientes hechos se suelen tomar como evidencia de la tesis:

Se conocen muchos modelos de computación equivalentes, y todos ellos dan la misma definición de función computable (o una versión más débil, en algunos casos).
No se ha propuesto ningún modelo de computación más robusto que se considere generalmente efectivamente calculable .

La tesis de Church-Turing se utiliza a veces en demostraciones para justificar que una función particular es computable, proporcionando una descripción concreta del procedimiento para su cálculo. Esto se permite porque se cree que todos estos usos de la tesis pueden eliminarse mediante el tedioso proceso de escribir un procedimiento formal para la función en algún modelo de cálculo.

Demostrabilidad

Dada una función (o, de forma similar, un conjunto), puede interesarnos no solo si es computable, sino también si esto puede demostrarse en un sistema de prueba particular (generalmente la aritmética de Peano de primer orden ). Una función que puede demostrarse que es computable se denomina demostrablemente total .

El conjunto de funciones demostrablemente totales es recursivamente enumerable : se pueden enumerar todas las funciones demostrablemente totales enumerando todas sus pruebas correspondientes, que demuestran su computabilidad. Esto se puede lograr enumerando todas las pruebas del sistema de prueba e ignorando las irrelevantes.

Relación con funciones definidas recursivamente

En una función definida mediante una definición recursiva , cada valor se define mediante una fórmula fija de primer orden de otros valores previamente definidos de la misma función u otras funciones, que podrían ser simplemente constantes. Un subconjunto de estas son las funciones recursivas primitivas . Otro ejemplo es la función de Ackermann , que se define recursivamente pero no es recursiva primitiva. ^{[ 5 ]}

Para que las definiciones de este tipo eviten la circularidad o la regresión infinita, es necesario que las llamadas recursivas a la misma función dentro de una definición sean a argumentos que sean más pequeños en algún orden parcial bien definido en el dominio de la función. Por ejemplo, para la función de Ackermann $A$ , siempre que la definición de $A(x,y)$ se refiere a $A(p,q)$ , entonces $(p,q)<(x,y)$ con respecto al orden lexicográfico en pares de números naturales . En este caso, y en el caso de las funciones recursivas primitivas, el buen ordenamiento es obvio, pero algunas relaciones de "referencia" no son triviales de probar como buenos ordenamientos. Cualquier función definida recursivamente de manera bien ordenada es computable: cada valor puede calcularse expandiendo un árbol de llamadas recursivas a la función, y esta expansión debe terminar después de un número finito de llamadas, porque de lo contrario el lema de Kőnig conduciría a una secuencia descendente infinita de llamadas, violando el supuesto de buen ordenamiento.

Funciones totales que no son demostrablemente totales

En un sistema de prueba sólido , toda función demostrablemente total es de hecho total, pero lo contrario no es cierto: en todo sistema de prueba de primer orden que sea suficientemente fuerte y sólido (incluida la aritmética de Peano), se puede probar (en otro sistema de prueba) la existencia de funciones totales que no se pueden probar como totales en el sistema de prueba.

Si las funciones computables totales se enumeran a través de las máquinas de Turing que las producen, entonces la afirmación anterior puede demostrarse, si el sistema de prueba es sólido, mediante un argumento de diagonalización similar al utilizado anteriormente, utilizando la enumeración de funciones demostrablemente totales dada anteriormente. Se utiliza una máquina de Turing que enumera las pruebas relevantes y para cada entrada n produce f _n ( n ) + 1 (donde f _n es la n -ésima función según esta enumeración) invocando la máquina de Turing que la calcula de acuerdo con la n -ésima prueba. Se garantiza que dicha máquina de Turing se detendrá si el sistema de prueba es sólido, pero la función total que calcula no puede ser ninguna de las funciones demostradas como totales por el sistema de prueba, de lo contrario habría algún n para el cual f _n ( n ) + 1 = f _n ( n ).

Funciones incomputables y problemas irresolubles

Cada función computable tiene un procedimiento finito que proporciona instrucciones explícitas e inequívocas sobre cómo calcularla. Además, este procedimiento debe estar codificado en el alfabeto finito utilizado por el modelo computacional, por lo que solo existe un número numerable de funciones computables. Por ejemplo, las funciones pueden codificarse mediante una cadena de bits (el alfabeto $Σ = {0, 1$ }).

Los números reales son incontables, por lo que la mayoría de ellos no son computables . El conjunto de funciones finitas sobre los números naturales es incontable, por lo que la mayoría no son computables. Ejemplos concretos de estas funciones son el problema del castor ocupado , la complejidad de Kolmogorov o cualquier función que devuelva los dígitos de un número no computable, como la constante de Chaitin .

De manera similar, la mayoría de los subconjuntos de los números naturales no son computables. El problema de la parada fue el primero en plantearse. El problema de decisión (Entscheidungsproblem ), propuesto por David Hilbert , indagaba si existía un procedimiento eficaz para determinar qué enunciados matemáticos (codificados como números naturales) eran verdaderos. Turing y Church demostraron independientemente en la década de 1930 que este conjunto de números naturales no es computable. Según la tesis de Church-Turing, no existe ningún procedimiento eficaz (con un algoritmo) que pueda realizar estos cálculos.

Extensiones de la computabilidad

Computabilidad relativa

La noción de computabilidad de una función puede relativizarse a un conjunto arbitrario de números naturales A. Una función f se define como computable en A (o equivalentemente A -computable o computable en relación con A ) cuando satisface la definición de función computable con modificaciones que permiten el acceso a A como oráculo . Al igual que con el concepto de función computable, la computabilidad relativa puede tener definiciones equivalentes en muchos modelos de computación diferentes. Esto se logra comúnmente complementando el modelo de computación con una operación primitiva adicional que pregunta si un entero dado pertenece a A. También podemos hablar de que f es computable en g identificando g con su grafo.

Teoría de recursión superior

La teoría hiperaritmética estudia los conjuntos que pueden calcularse a partir de un número ordinal computable de iteraciones del salto de Turing del conjunto vacío. Esto equivale a conjuntos definidos por una fórmula universal y existencial en el lenguaje de la aritmética de segundo orden y a algunos modelos de hipercomputación . Incluso se han estudiado teorías de recursión más generales, como la teoría de la recursión E, en la que cualquier conjunto puede utilizarse como argumento de una función recursiva E.

Hipercomputación

Si bien la tesis de Church-Turing afirma que las funciones computables incluyen todas las funciones con algoritmos, es posible considerar clases de funciones más amplias que flexibilizan los requisitos que deben cumplir los algoritmos. El campo de la hipercomputación estudia modelos de computación que van más allá de la computación de Turing convencional.

Véase también

Referencias

↑ Enderton, Herbert (2002). Introducción matemática a la lógica (Segunda edición). EE. UU.: Elsevier. pág. 209. ISBN 0-12-238452-0.
↑ Enderton, Herbert (2002). Introducción matemática a la lógica (Segunda edición). EE. UU.: Elsevier. págs. 208, 262. ISBN 0-12-238452-0.
↑ CJ Ash, J. Knight, Estructuras computables y la jerarquía hiperaritmética (Estudios en lógica y fundamentos de las matemáticas, 2000), pág. 4
↑ R. Soare, Computabilidad y recursión. Archivado el 31 de marzo de 2022 en Wayback Machine (1995). Consultado el 9 de noviembre de 2022.
^ Peter, Rózsa (1935). "Konstruktion nichtrekursiver Funktionen". Annalen Matemáticas . 111 : 42– 60. doi : 10.1007/BF01472200 . S2CID 121107217 .

Cutland, Nigel. Computabilidad . Cambridge University Press, 1980.
Enderton, HB Elementos de la teoría de la recursión. Manual de lógica matemática (North-Holland 1977) pp. 527–566.
Rogers, H. Teoría de las funciones recursivas y la computación efectiva (McGraw–Hill 1967).
Turing, A. (1937), Sobre los números computables, con una aplicación al problema de decisión . Actas de la Sociedad Matemática de Londres , Serie 2, Volumen 42 (1937), págs. 230-265. Reimpreso en M. Davis (ed.), Lo indecidible , Raven Press, Hewlett, NY, 1965.

[1] Enderton, Herbert (2002). Introducción matemática a la lógica (Segunda edición). EE. UU.: Elsevier. pág. 209. ISBN 0-12-238452-0.

[2] Enderton, Herbert (2002). Introducción matemática a la lógica (Segunda edición). EE. UU.: Elsevier. págs. 208, 262. ISBN 0-12-238452-0.

[3] CJ Ash, J. Knight, Estructuras computables y la jerarquía hiperaritmética (Estudios en lógica y fundamentos de las matemáticas, 2000), pág. 4

[4] R. Soare, Computabilidad y recursión. Archivado el 31 de marzo de 2022 en Wayback Machine (1995). Consultado el 9 de noviembre de 2022.

[5] Peter, Rózsa (1935). "Konstruktion nichtrekursiver Funktionen". Annalen Matemáticas . 111 : 42– 60. doi : 10.1007/BF01472200 . S2CID 121107217 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]